题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0），n<=39。

三种解法：

1.递归

看到斐波那契数列的公式，第一想法也许就是递归，这样想着关键代码两三行就搞定了，注意这题的n是从0开始的：

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=1) return n;
        else return Fibonacci(n-1)+Fibonacci(n-2);
    }
};

然而并没有什么用，测试用例里肯定准备着一个超大的n来让Stack Overflow，为什么会溢出？因为重复计算，而且重复的情况还很严重，举个小点的例子，n=4，看看程序怎么跑的：

Fibonacci(4) = Fibonacci(3) + Fibonacci(2);

                    = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

                    = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

对于程序来说它每次递归都是未知的，因此光是n=4时f(1)就重复计算了3次之多。

• 递归：函数自己调用自己

• 递归的"缺陷"：递归到一定程度，会发生"栈溢出"

• 递归的"时间复杂度"：递归总次数*每次递归的次数

• 递归的"空间复杂度"：递归的深度*每次递归空间的大小（注意："每次递归空间的大小"是个常数，可以基本忽略不计）

• 递归的"深度"：树的高度（递归的过程是一个"二叉树"）

                              

此种方法的缺陷：重复计算的次数太多，效率低，时间复杂度：O(2^N)，空间复杂度：O(N)

2、尾递归——解决重复计算的问题

什么是尾递归？最后返回值直接等于递归函数的结果，不用等上一步递归结果再运算，运算过程放在了输入参数里。覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，可参考https://www.cnblogs.com/catch/p/3495450.html 。

public class Solution {
    public int Fibonacci(int n) {
        return Fibonacci(n,0,1);
    }
     
     
    private static int Fibonacci(int n,int acc1,int acc2){
        if(n==0) return 0;
        if(n==1) return acc2;
        else     return Fibonacci(n - 1, acc2, acc1 + acc2);
         
    }
}

此种方法是尾递归，很大程度的减小了第一种方法（递归实现斐波那契数列）的时间复杂度
时间复杂度：O(N-2)约等于0(N)
空间复杂度：O(N-2)约等于0(N)（编译器如果优化的话是O（1））
 

3、循环

首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O(n)，空间复杂度O(1)。

class Solution {
public:
    int Fibonacci(int n) {
        int f1=0,f2=1;
        while(n--){
            f2=f1+f2;
            f1=f2-f1;
        }
        //从0开始，有第0项为0
        return f1;
    }
};