等差数列，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 = ;

        for (int i = ; i < n + ; 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 = ( + n) * n / ;

        return s;

    }

    /// <summary>

    /// 递归

    /// </summary>

    /// <param name="n"></param>

    /// <param name="counter"></param>

    /// <returns></returns>

    public int TestRec(int n)

    {

        if (n == ) return ;

        return n + TestRec(n - );

    }

    /// <summary>

    /// 尾递归

    /// </summary>

    /// <param name="n"></param>

    /// <param name="counter"></param>

    /// <returns></returns>

    public int TestTail(int n)

    {

        return TestTail(, n);

    }

    public int TestTail(int sum, int n)

    {

        if (n == ) return sum;

        sum = sum + n;

        return TestTail(sum, n - );

    }

}

基准测试

[SimpleJob(RuntimeMoniker.NetCoreApp30)]

[RPlotExporter]

public class TestClassForBenchmark

{

    private readonly TestClass testClass = new TestClass();

    [Params(,,,)]

    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 = ;

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测试结果

. 10次

结果：,TestFor时间:

结果：,TestForG时间:

结果：,TestRec时间:

结果：,TestTail时间:

.

结果：,TestFor时间:

结果：,TestForG时间:

结果：,TestRec时间:

结果：,TestTail时间:

.

结果：,TestFor时间:

结果：,TestForG时间:

结果：,TestRec时间:

结果：,TestTail时间:

.

结果：,TestFor时间:

结果：,TestForG时间:

结果：,TestRec时间:

结果：,TestTail时间:

.

结果：,TestFor时间:

结果：,TestForG时间:

结果：,TestRec时间:

结果：,TestTail时间:

结论

1. for的运行速度比递归快，但是递归结构比较清晰，容易理解。

2. 等差计算不一定比for循环快

斐波那契数列对比

        /// <summary>

        /// 循环实现 counter:运行次数

        /// </summary>

        public long Fib(int n, ref int counter)

        {

            if (n < ) return ;

            long a = , b = ;

            long temp;

            for (int i = ; 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 < ) return ;

            if (n < ) return ;

            return FibRec(n - , ref counter) + FibRec(n - , ref counter);

        }

        /// <summary>

        /// 尾递归实现

        /// </summary>

        public long FibTailRec(int n, ref int counter)

        {

            if (n < ) return ;

            if (n < ) return ;

            return FibRec(, , n, ref counter);

        }

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

        {

            counter++;

            long temp = last + prev;

            if (n == ) return temp;

            last = prev;

            prev = temp;

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

        }

效果

counter是运行的次数，斐波那契数列直接用递归，n=100都直接堆栈溢出。递归用的好了，思路清晰，用的不好的话，数据稍微大点就是深深的坑。用递归尽量优化为尾递归，也就是返回的时候调用自身，不要有表达式。

巴特西