递归写法慢是因为重复计算导致时间复杂度达o(2ⁿ)，如fib(40)需约3.3×10⁸次调用，fib(35)被反复计算上百次，指数级增长使fib(50)几乎不可行。
递归写法为什么慢得离谱
直接用 fib(n) = fib(n-1) + fib(n-2) 递归，fib(40) 就要算几千万次调用——因为重复计算太多。比如 fib(35) 会被反复算上百遍。这不是写法错，是算法复杂度爆炸：O(2^n)，实际运行时连 fib(50) 都可能卡住。
实操建议：
- 仅用于教学演示或
n 的极小值场景 - 加记忆化（memo）能救回来，但不如直接换迭代
- 别在生产代码里裸写这种递归
迭代法是最稳的入门解法
用两个变量滚动更新，时间 O(n)、空间 O(1)，无栈溢出风险，适合绝大多数需求。
示例（处理边界和溢出）：
long long fib(int n) {
if (n <p>注意点：</p>
- 用
long long而非int，fib(47)就超int最大值 - 输入校验不能少，
n为负时行为要明确 - 循环从
i = 2开始，避免多算一次
矩阵快速幂适合大 n 场景
当需要算 fib(10^6) 或更高，且不能接受 O(n) 时间时，用矩阵快速幂能把复杂度压到 O(log n)。核心是把递推转成矩阵幂：[fib(n), fib(n-1)]^T = [[1,1],[1,0]]^(n-1) * [fib(1), fib(0)]^T。
实操关键：
- 必须手写
mat_mul和mat_pow，标准库没现成矩阵类型 - 每次乘法后立即取模（如需模
1e9+7），否则中间结果溢出 - 指数为 0 或 1 时要特判，不然
mat_pow容易崩 - 比迭代法难调试，除非真有性能瓶颈，否则不值得上
编译期计算用 constexpr 搞定小值
如果 n 是编译期常量（比如模板参数或字面量），C++11 起就能用 constexpr 递归，在编译时算出结果，运行时零开销。
示例：
constexpr long long fib(int n) {
return n <p>限制很硬：</p>
-
n必须是常量表达式，fib(i)（i是变量）会编译失败 - 递归深度受编译器限制（GCC 默认 512 层），
fib(1000)直接报错 - 只适用于已知小
n且要嵌入常量上下文的场合，比如数组长度、枚举值
真正麻烦的是溢出控制和输入范围检查——不管用哪种方法，fib(94) 就超过 long long 最大值，这点很容易被忽略。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
