[C#]遞迴與迴圈的時間測試

2017-09-21

2456
0
C#

在大學的時候就聽過"遞迴其實速度比較慢"的觀念，但是都沒有做過實作，這篇文章是我以費氏函數為例子的測試。

遞迴的函式

        static double resFin(int fin)
        {
            if (fin == 1 || fin == 2) return 1;
            return resFin(fin - 1) + resFin(fin - 2);
        }

迴圈的函式

        static double listFin(int fin)
        {
            List<double> finlist = new List<double> { 1, 1 };
            for (int i = 2;i <fin;i++)
            {
                finlist.Add(finlist[i - 1] + finlist[i - 2]);
            }
            return finlist[fin - 1];
        }

測試的程式碼

		static void Main(string[] args)
		{
            int fin = n;
            Console.WriteLine("n = "+ fin.ToString());
            DateTime Start;
            Start = DateTime.Now;

            Console.WriteLine(resFin(fin) +" " + (DateTime.Now - Start).TotalMilliseconds);
            Start = DateTime.Now;

            Console.WriteLine(listFin(fin) + " " + (DateTime.Now - Start).TotalMilliseconds);
            Start = DateTime.Now;
            Console.ReadKey();
        }

n為費氏的項目，我們進行四次的測試，n分別為5、20、30、40

可以發現，當n的次數變大的時候，遞迴的使用時間會迅速的增加，而迴圈並不會增加。

回首頁