尾递归与斐波那契三种解法_斐波那契 尾递归

常规的斐波那契数列解法

int fib(int n) {
    if (n <= 2) {
        return 1;
    }
    else
        return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5
6
7

要求第n个斐波那契数，子问题就是求每一个斐波那契数的前一项和前二项之和，典型的递归思想。

这个算法的时间复杂度怎么算呢？

递归的时间复杂度：递归次数*一次递归的基本语句执行次数

递归的空间复杂度：在栈空间最大的临时变量个数

如果求f(5),画出调用过程就是

              f(5)
       f(4)          f(3)
    f(3)  f(2)      f(2) f(1)
f(2) f(1)
1
2
3
4

一个树状结构，先从f5->f4->f3-f2->f1->f2左子树就递归完了。每一个结点都是一次递归，每一个递归里只有一个基本语句，而结点书大约等与2^(N-2)常数忽略也就是2^N次递归调用，所以时间复杂度O(2^n).

空间复杂度由图可以看出f5->f2之后递归f1，之后归值给f3，这时f2和f1的空间已经回收了，所以最大的空间占用也只是f5->f1, 即O(n)。

循环优化斐波那契

int fib(int n) {
    int pre = 1;
    int ppre = 0;
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        ret = pre + ppre;
        ppre = pre;
        pre = ret;
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11

循环迭代的精髓是每次计算的结果参与下次的计算，这种解法也是最优的，时间O(n),空间O（1）.

尾递归优化斐波那契

int fib(int n, int ppre, int pre) {
    if (n <= 1)
        return ppre;
    return fib(n - 1, pre, ppre + pre);
}
int main()
{
    int ret = fib(5, 1, 1);
}
1
2
3
4
5
6
7
8
9

递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。

尾递归的精髓就是吸取循环的精华——把每次计算的结果当作参数传递给下一次计算。

调用过程如图，时间复杂度就是O（n），如果编译器优化空间复杂度O（1）.