等差數列，for迴圈，遞歸和尾遞歸的對比

生活中，如果1+2+3+4.....+100，大家基本上都會用等差數列計算，如果有人從1開始加，不是傻就是白X，那麼程式中呢，是不是也是這樣。今天無意中看到了尾遞歸，以前也寫過，但是不知道這個專業名詞，今天寫一下對比下性能問題。

今天主要是看到了尾遞歸，所以聯想到了這些，寫下這篇文章，其中也把Benchmark (Nuget上的BenchmarkDotNet)的基準測試用了下，感覺比較好用，贊。Benchmark 需要在release下運行。

原則上所有的遞歸操作，都可以寫成迴圈操作。尾遞歸是指，在函數返回的時候，調用自身本身，並且return語句不能包含表達式。這樣編譯器或者解釋器就可以把尾遞歸做優化，試運行速度更快。

測試類

public class TestClass
{
    /// <summary>
    /// for迴圈
    /// </summary>
    /// <param name="n"></param>
    /// <param name="counter"></param>
    /// <returns></returns>
    public int TestFor(int n)
    {
        int s = 1;

        for (int i = 2; i < n + 1; i++)
        {
            s = s + i;
        }

        return s;
    }

    /// <summary>
    /// 等差數列
    /// </summary>
    /// <param name="n"></param>
    /// <param name="counter"></param>
    /// <returns></returns>
    public int TestForG(int n)
    {
        int s = (1 + n) * n / 2;

        return s;
    }

    /// <summary>
    /// 遞歸
    /// </summary>
    /// <param name="n"></param>
    /// <param name="counter"></param>
    /// <returns></returns>
    public int TestRec(int n)
    {
        if (n == 1) return 1;
        return n + TestRec(n - 1);
    }

    /// <summary>
    /// 尾遞歸
    /// </summary>
    /// <param name="n"></param>
    /// <param name="counter"></param>
    /// <returns></returns>
    public int TestTail(int n)
    {
        return TestTail(1, n);
    }

    public int TestTail(int sum, int n)
    {
        if (n == 1) return sum;
        sum = sum + n;
        return TestTail(sum, n - 1);
    }
}

基準測試

[SimpleJob(RuntimeMoniker.NetCoreApp30)]
[RPlotExporter]
public class TestClassForBenchmark
{
    private readonly TestClass testClass = new TestClass();

    [Params(100,500,1000,5000)]
    public int N;

    [Benchmark]
    public void TestFor()
    {
        testClass.TestFor(N);
    }

    [Benchmark]
    public void TestForG()
    {
        testClass.TestForG(N);
    }

    [Benchmark]
    public void TestRec()
    {
        testClass.TestRec(N);
    }

    [Benchmark]
    public void TestTail()
    {
        testClass.TestTail(N);
    }

}

Main程式調用

BenchmarkRunner.Run<TestClassForBenchmark>();

結果

用Benchmark的基準測試發現，運行時間：等差 < for < 尾遞歸(接近for) < 遞歸，for的運行速度比遞歸快，但是遞歸結構比較清晰，容易理解。

發現TestForG有點問題，接下來自己簡單測試

實際用Stopwatch測試

TestClass testClass = new TestClass();

Stopwatch stopSwitch = new Stopwatch();
int n = 5000;
stopSwitch.Start();
int sum = testClass.TestFor(n);
stopSwitch.Stop();
Console.WriteLine($"結果：{sum},TestFor時間:{stopSwitch.ElapsedTicks}");

stopSwitch.Start();
sum = testClass.TestForG(n);
stopSwitch.Stop();
Console.WriteLine($"結果：{sum},TestForG時間:{stopSwitch.ElapsedTicks}");

stopSwitch.Restart();
sum = testClass.TestRec(n);
stopSwitch.Stop();
Console.WriteLine($"結果：{sum},TestRec時間:{stopSwitch.ElapsedTicks}");

stopSwitch.Restart();
sum = testClass.TestTail(n);
stopSwitch.Stop();
Console.WriteLine($"結果：{sum},TestTail時間:{stopSwitch.ElapsedTicks}");

Stopwatch測試結果

1. 10次
結果：55,TestFor時間:2024
結果：55,TestForG時間:3799
結果：55,TestRec時間:1603
結果：55,TestTail時間:2371

2. 100
結果：5050,TestFor時間:1704
結果：5050,TestForG時間:2708
結果：5050,TestRec時間:1069
結果：5050,TestTail時間:1401
3. 500
結果：125250,TestFor時間:1794
結果：125250,TestForG時間:3096
結果：125250,TestRec時間:9398
結果：125250,TestTail時間:2332
4. 1000
結果：500500,TestFor時間:2080
結果：500500,TestForG時間:4147
結果：500500,TestRec時間:2003
結果：500500,TestTail時間:2540
5. 5000
結果：12502500,TestFor時間:1428
結果：12502500,TestForG時間:3982
結果：12502500,TestRec時間:6815
結果：12502500,TestTail時間:2799

結論

1. for的運行速度比遞歸快，但是遞歸結構比較清晰，容易理解。

2. 等差計算不一定比for迴圈快

斐波那契數列對比

        /// <summary>
        /// 迴圈實現 counter:運行次數
        /// </summary>
        public long Fib(int n, ref int counter)
        {
            if (n < 1) return 0;
            long a = 1, b = 1;
            long temp;
            for (int i = 3; i <= n; i++)
            {
                counter++;
                temp = a;
                a = b;
                b = temp + b;
            }

            return b;
        }

        /// <summary>
        /// 遞歸實現
        /// </summary>
        public long FibRec(int n, ref int counter)
        {
            counter++;
            if (n < 1) return 0;
            if (n < 3) return 1;
            return FibRec(n - 1, ref counter) + FibRec(n - 2, ref counter);
        }

        /// <summary>
        /// 尾遞歸實現
        /// </summary>
        public long FibTailRec(int n, ref int counter)
        {
            if (n < 1) return 0;
            if (n < 3) return 1;
            return FibRec(1, 1, n, ref counter);
        }

        public long FibRec(long last, long prev, int n, ref int counter)
        {
            counter++;

            long temp = last + prev;
            if (n == 3) return temp;
            last = prev;
            prev = temp;

            return FibRec(last, prev, n - 1, ref counter);
        }

效果

counter是運行的次數，斐波那契數列直接用遞歸，n=100都直接堆棧溢出。遞歸用的好了，思路清晰，用的不好的話，數據稍微大點就是深深的坑。用遞歸儘量優化為尾遞歸，也就是返回的時候調用自身，不要有表達式。