c++中如何计算斐波那契数列_c++递归实现斐波那契

递归实现斐波那契时间复杂度为O(2^n)，存在大量重复计算，n>40时显著变慢，n>100时易因递归深度过大导致栈溢出或段错误。

为什么递归实现 fibonacci 在 C++ 中容易超时或栈溢出

直接用递归写 fibonacci(n) 看似简洁，但时间复杂度是 O(2^n)。因为每次调用都分裂成两个子调用，大量重复计算（比如 fib(3) 会被算很多次）。当 n 超过 40，fib(45) 就可能卡住；n > 100 时，递归深度远超默认栈空间，触发 Segmentation fault (core dumped) 或 stack overflow。

• 不要在生产或竞赛代码中直接用裸递归算 fibonacci
• 即使加了 if (n 边界判断，也无法改善指数级膨胀
• 编译器几乎不会对这种朴素递归做尾调用优化（C++ 标准不保证）

如何用记忆化递归（Memoization）安全地保留递归结构

在递归基础上缓存已算结果，把重复计算从“指数级”降到“线性级”。关键是在函数外或传入一个 std::vector 作为缓存容器，下标即 n 值。

long long fib_memo(int n, std::vector& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
    return memo[n];
}

// 使用示例：
std::vector memo(100, -1); // 预分配 100 个位置
long long result = fib_memo(50, memo);

• memo 必须初始化为无效值（如 -1），不能用 0——因为 fib(0) == 0
• 注意 long long 防止 int 溢出：第 48 项就超过 int 最大值
• 如果 n 可能很大（如 1e6），改用动态规划迭代更稳妥（避免栈深度）

迭代法才是 C++ 中最实用的实现方式

用两个变量滚动更新，空间 O(1)、时间 O(n)、无栈风险，且编译器容易优化成极简汇编。

long long fib_iter(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

• 不需要容器、不依赖递归深度，n = 1000000 也能秒出结果（数值会溢出，但逻辑不崩）
• 若需模运算（如 fib(n) % 1000000007），直接在每次加法后取模即可
• 别用 std::pow 或矩阵快速幂来“炫技”——除非 n 是 1e18 级别且要求 O(log n)

调试时遇到 fibonacci 输出异常的常见原因

不是算法错，往往是类型或边界没兜住：

• int fib(int n) → 第 47 项开始溢出，输出负数或乱码
• 递归没写 if (n ，导致无限调用直到栈满
• 用 unsigned int 但忘了 0 和 1 是合法输入，n-2 可能回绕成极大正数
• 忘记处理负数输入：fib(-1) 应该报错或返回 0？C++ 不检查数组越界，memo[-1] 直接 UB

真正写进工程代码前，先想清楚 n 的取值范围、是否需要大数、是否要线程安全——递归只是教学模型，不是解法本身。