题解 | #斐波那契数列#

解题思路：使用递归实现斐波那契数列。

时间复杂度：O(2^n)，执行次数最多不超过高度为n的满二叉树的节点数（2^n-1）；

空间复杂度：O(n)，递归使用的栈的大小;

补充：在递归计算的过程中，有很多节点是重复计算的，而且重复的节点数会随着n的增大而急剧增加，这意味这计算量会随着n的增大而急剧增大。

递归的缺点：递归由于是函数调用自身，而函数调用是有时间和空间的消耗的，每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间；除了效率之外，递归还存在调用栈溢出的问题，需要为每一次函数调用在内存栈中分配空间，而每个进程的栈容量是有限的，当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。

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

解题思路：递归求解有很多重复的计算，为了避免重复计算，可以把已经得到的数列的中间项存起来，下次需要计算的时候先进行查找，如果前面已经计算过的就不用再重复计算了。更简单的办法是从下往上计算，首先根据f(1)和f(2)计算出f(3)，再根据f(2)和f(3)计算出f(4)……以此类推就可以算出第n项了。这样时间复杂度为O(n),空间复杂度为O(1)。

class Solution {
public:
    int Fibonacci(int n) {
        if(n==1 || n==2){
            return 1;
        }
        int fN_1 = 1, fN_2 = 1;
        int fN=0;
        for(int i=3; i<=n; ++i){
            fN = fN_1 + fN_2;
            fN_2 = fN_1;
            fN_1 = fN;
        }
        return fN;
    }
};