【基础算法】递归函数-斐波那契数列实现的优化-创新互联

递归学习

函数会递归调用自身
需要有退出条件，避免无限自调，导致堆栈溢出，程序奔溃

专注于为中小企业提供网站设计制作、网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业闽清免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了近1000家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。斐波那契数列

设数列{an}, 若满足a0=0, a1=1,an=an-1+an-2(n>=2)
则称数列{an}为斐波那契数列。

递推公式: a0=0, a1=1,an=an-1+an-2(n>=2)

实现方法1：普通递归实现

int fib(int n)
    {
        return n< 2 ? n : fib(n-1) + fib(n-2);
    }

当n比较大时，会导致两个问题：
1、递归的深度大，耗时长；
2、最终的结果有可能超出int的大范围

使用局部静态来优化：

对于已计算出来的结果直接返回即可，
不在已计算范围内的，据递推公式从原有基础上递推到n，并保留中间有效计算结果

如果int 类型不满足大范围，可以将int 改为long long int

int fb(int n)
{
    static vectorfb{0, 1};

    if (n< fb.size()) {
        return fb[n];
    }

    int size = fb.size();
    for (int i = size; i<= n; i++) {
        fb.push_back(fb[i - 1] + fb[i - 2]);
    }
    return fb[n];
}

延伸学习
int的上限问题
C/C++如何得到int型大值
https://blog.csdn.net/wenzishou/article/details/44563387

MIN_INT = (((unsigned int)(-1))>>1)
在32位系统中 2^(32-1) = 2147483647

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：【基础算法】递归函数-斐波那契数列实现的优化-创新互联
标题链接：http://bzwzjz.com/article/diphje.html