参考书籍： 《数据结构（C++语言版）》作者：邓俊辉
内容： 计算斐波那契数 知识点： 递归

问题

计算第n个斐波那契数

解答

这是学习递归最经典的一个问题，最直接的解法如下。

c++
int fib(int n){
    /*
    最经典的递归算法，由斐波那契数列的递推式得到
    */

    if(n==1 || n==2){return 1;}
    return fib(n-1) + fib(n-2);
}

但是以上算法有很多冗余无用的计算，导致复杂度来到了 $O(2^n)$ ，以下采取记忆的方法，得到复杂度为 $O(n)$ 的算法。

c++
int fib1(int n, int& prev){
    /*
    采用记忆的方法，存储会用到的数据，使时间复杂度变为O(n)
    */

    if(n==1){
        prev = 0;
        return 1;
    }

    int prevPrev;
    prev = fib1(n-1, prevPrev);
    return prev + prevPrev;
}

其实还存在 $O(\log{n})$ 的算法，感兴趣可自行了解。