递归实现斐波那契时间复杂度为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 输出异常的常见原因
不是算法错，往往是类型或边界没兜住：
立即学习“C++免费学习笔记（深入）”；
-
int fib(int n)→ 第 47 项开始溢出，输出负数或乱码 - 递归没写
if (n ，导致无限调用直到栈满 - 用
unsigned int但忘了0和1是合法输入，n-2可能回绕成极大正数 - 忘记处理负数输入：
fib(-1)应该报错或返回 0？C++ 不检查数组越界，memo[-1]直接 UB
真正写进工程代码前，先想清楚 n 的取值范围、是否需要大数、是否要线程安全——递归只是教学模型，不是解法本身。
