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

递归学习

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

专注于为中小企业提供网站设计制作、网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业闽清免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了近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://myzitong.com/article/diphje.html