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

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

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

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

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元起，快前往官网查看详情吧