递归实现的斐波那契数列代码n>40时运行过慢，求优化方案

算力阿峰

2026-9-29

代码问题说明

你提供的代码不存在语法或逻辑错误，输出结果完全正确。运行耗时长是朴素递归实现斐波那契数列的固有缺陷：
这种实现会产生大量重复计算，例如计算fib(5)时需要重复计算2次fib(3)、3次fib(2)，n越大重复计算的量级越高，整体时间复杂度为指数级O(2ⁿ)，当n=50时需要执行的运算次数已经超过千亿次，自然会出现明显卡顿。

可行优化方案

方案1：记忆化递归（顶向下动态规划）
新增数组/哈希表存储已经计算过的斐波那契值，遇到重复计算需求时直接读取存储的结果，无需重复递归，时间复杂度降为O(n)。
示例代码：

#include<iostream>
#include<vector>
using namespace std;

vector<long int> memo;
long int fib(int a)
{
    if(a<=1) return a;
    if(memo[a] != 0) return memo[a];
    memo[a] = fib(a-1) + fib(a-2);
    return memo[a];
}
int main()
{
    int n;
    cin>>n;
    memo.resize(n+1, 0);
    cout<<fib(n);
    return 0;
}

方案2：迭代实现（底向上动态规划，空间优化版）
放弃递归逻辑，从fib(0)、fib(1)开始逐步向上推导到fib(n)，且仅存储前两项的计算结果，空间复杂度压到O(1)，是工程中最常用的实现方案。
示例代码：

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    if(n<=1) {
        cout<<n;
        return 0;
    }
    long int prev_prev = 0, prev = 1, curr;
    for(int i=2; i<=n; i++){
        curr = prev_prev + prev;
        prev_prev = prev;
        prev = curr;
    }
    cout<<prev;
    return 0;
}