c++怎么实现斐波那契数列_c++递归与迭代对比【教程】

递归写法慢因重复计算子问题致O(2^n)时间复杂度，易卡顿、栈溢出；推荐滚动变量迭代法，O(n)时间、O(1)空间且无栈风险。

递归写法为什么慢得明显

因为 fib(n) 会重复计算大量子问题，比如 fib(5) 调用 fib(3) 两次，fib(4) 又调用一次——指数级调用栈，时间复杂度是 O(2^n)。

常见错误现象：fib(45) 就卡顿，fib(50) 等好几秒，还可能栈溢出（尤其没开尾递归优化时）。

实操建议：

• 别在生产代码里直接用裸递归算斐波那契，哪怕只是练手也该意识到它不可扩展
• 如果非要递归，加个 std::map 缓存结果（记忆化），但这时不如直接改迭代
• 编译器基本不给 fib 做尾递归优化，别指望 return fib(n-1) + fib(n-2) 被转成循环

迭代实现最稳当的写法

用两个变量滚动更新，空间 O(1)、时间 O(n)，没有栈风险，整数溢出前都能跑。

立即学习“C++免费学习笔记（深入）”；

使用场景：嵌入式、高频调用、需要确定性性能的地方。

实操建议：

• 别用数组存全部中间值，除非你真要返回整个序列
• 注意初始条件：fib(0) == 0，fib(1) == 1，别写反
• int 很快溢出（fib(47) 就超 INT_MAX），推荐用 long long 或 unsigned long long

简短示例：

long long fib(int n) {     if (n < 2) 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; }

用 std::vector 预计算适合多次查询

如果你的程序要反复查不同 n 的斐波那契值（比如做 DP 预处理、游戏资源表），一次性算到最大需要的 n，之后全是 O(1) 查表。

性能影响：初始化略慢，但后续零开销；内存占用和最大 n 成正比。

实操建议：

• 别在函数里每次重分配 std::vector，用 Static 局部变量缓存
• 提前预留容量：v.reserve(MAX_N + 1)，避免多次 realloc
• 检查越界：查 v[n] 前确保 n ，否则触发未定义行为

溢出检测不能靠事后判断

c++ 不自动捕获整数溢出，a + b 溢出后结果是未定义行为（UB），不是简单变负数或截断。

容易踩的坑：用 if (c 判断溢出 —— 对无符号类型无效，对有符号类型是 UB 后的不可靠表现。

实操建议：

• 用 和比较代替运算：if (b > std::numeric_limits::max() - a)
• 更稳妥用 std::add_overflow（C++23）或第三方库如 absl::int128 处理大数
• 如果业务允许，直接限定输入范围（比如只支持 n ，对应 unsigned long long 最大值）

真正麻烦的从来不是“怎么写出来”，而是想清楚你要的是单次快速响应、还是批量查表、还是带溢出安全的健壮接口——选错方案，后面全是补丁。