斐波那契数列

波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144，是指这样一个数列

递推公式如图：

1.最常见递归算法

 //最常见的递归
  static int Fibo(int n)
   {
       if (n == 1 || n == 2)
            return 1;
        else
             return Fibo(n - 2) + Fibo(n - 1);
     }

但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。

注意：递归代码要警惕重复计算

除此之外，使用递归时还会出现重复计算的问题。刚才我讲的第二个递归代码的例子，如果我们把刚才我讲的第二个递归代码的例子，如果我们把整个递归过程分解一下的话，那就是这样的：

 n 越大，这段代码执行效率越低

执行结果：n:40,result:102334155,耗时:2470

我们会发现f(n)这个方法被调用了很多次，而且其中重复率非常之高，也就是说被重复计算了很多次，如果n稍微大一点这棵树会非常庞大。这里我们可以看出，每个节点就需要计算一次，总计算的次数就是该二叉树节点的数量，可见其时间复杂度为O(2^n)，是指数级的，其空间复杂度也就是该二叉树的高度，为O(n)。这样来看，我们应该就清楚了，为什么这段代码效率如此低下了吧。

2.数组保存法

        //数组保存法
        static long Fibo2(int n)
        {
            long[] fib = new long[n];
            fib[0] = 1;
            fib[1] = 1;
            for (int i = 2; i < n; i++)
            {
                fib[i] = fib[i - 2] + fib[i - 1];
            }
            return fib[n - 1];
        }

执行结果：n:40,result:102334155,耗时:0

时间复杂度和空间复杂度都为O(n)

3.滚动数组法

 static long Fibo3(int n)
        {
            long first = 1;
            long second = 1;
            long third = 2;
            if (n <= 2)
                return 1;
            else
            {
                for (int i = 3; i <= n; i++)
                {
                    third = first + second;
                    first = second;
                    second = third;
                }
                return third;
            }
        }

时间复杂度仍然为O(n)，而空间复杂度为常量级别3，即空间复杂度为0

参考链接：https://mp.weixin.qq.com/s/UfNS80v_AdWGO7md83r8ng