递归 | 高性能架构探索

#include <iostream>
using namespace std;

//斐波拉契数列是这样一个数列：1, 1, 2, 3, 5, 8
int Fib(int n){
    if (n == 1 || n == 2){
        return 1;
    }
    else{
        return Fib(n - 1) + Fib(n - 2);
    }
}
//不使用递归
int myFib(int n){

    if (n == 1 || n == 2){
        return 1;
    }
    int prev = 0;
    int cur = 1;
    for (int i = 0; i < n-1; i++){
        int temp = cur;
        cur = prev + cur;
        prev = temp;
    }
    return cur;
}

int main(void)
{
    cout << Fib(7) << endl;
    cout << myFib(7) << endl;
}

这种递归的写法看起来简洁明了，但是上面写法有一个问题：我们要求F(100)，那么要计算F(99)和F(98)；要计算F(99)，我们要计算F(98)和F(97)。。。大家已经发现到这一步，我们已经重复计算两次F(98)了。而之后的计算中还会有大量的重复，这使得这个解法的复杂度非常之高。解决方法就是，用一个数组，将计算过的值存起来，这样可以用空间上的牺牲来换取时间上的效率提高

int Fib(int n){


    if (n == 1 || n == 2){
        return 1;
    }
    if (array[n - 1] != 0){
        return array[n - 1];
    }
    array[n - 1] = Fib(n - 1) + Fib(n - 2);
    return array[n - 1];
}

动态转移虽然看上去十分高大上，但是它也存在两个致命缺点：

栈溢出 ：每一次递归，程序都会将当前的计算压入栈中。随着递归深度的加深，栈的高度也越来越高，直到超过计算机分配给当前进程的内存容量，程序就会崩溃。
数据溢出 ：因为动态规划是一种由简至繁的过程，其中积蓄的数据很有可能超过系统当前数据类型的最大值，导致崩溃。

当然，这两个bug也有相应的解决方法。对付栈溢出，我们可以把递归写成循环的形式（ 所有的递归都可改写成循环 ）；对付数据溢出，我们可以使用动态数组，vector来解决。

具体实例请参考动态规划相关

http://www.cnblogs.com/yuguangyuan/p/5835866.html

原文链接: https://www.cnblogs.com/yuguangyuan/p/5834078.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/398226

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

递归

相关推荐