为了性能，慎用递归

卧闲听云语聪睿

慎用递归

起因：

在学习Rust的时候，有一道语法练习题是计算斐波那契数列的第N项的值，这是一道非常简单的题，但是引发了一个使用递归性能问题，考虑到用Rust的人不多，后面的代码都是C#的，因为C#的语法更大众一些，更好看懂
第一次解

1. public static ulong FibonacciNumberRecursion(int n)
2. {
3.     if (n == 1)
4.         return 0;
5.     else if (n == 2)
6.         return 1;
7.     else
8.     {
9.         return FibonacciNumberRecursion(n - 1) + FibonacciNumberRecursion(n - 2);
10.     }
11. }

复制代码

这个写法非常的符合大脑思考，第一项返回0，第二项返回1，后面的返回前两项之和，简单测试没有任何问题。但是，这个算法有非常严重的性能问题，当n到40的时候，计算速度已经到了肉眼不可接受的地步，再往上就到了分钟级的了，造成运行缓慢的原因，就是递归会不停的压栈，存储当前的状态，这是非常没有必要的，于是我写了第二种解法
第二次解

[code]public static ulong FibonacciNumber(int n){    if (n == 1)        return 0;    else if (n == 2)        return 1;    else    {        var x = 3;        ulong xSub1 = 1;        ulong xSub2 = 0;        ulong value = 0;        while (x