生活中，如果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都直接堆栈溢出。递归用的好了，思路清晰，用的不好的话，数据稍微大点就是深深的坑。用递归尽量优化为尾递归，也就是返回的时候调用自身，不要有表达式。
黄山市民网：https://www.huangshanshimin.com/
