递归写法因重复计算导致时间复杂度达O(2^n)，n>40即明显卡顿；应优先选用迭代法，时间O(n)、空间O(1)、无栈溢出风险，并注意边界和long long溢出。
递归写法为什么慢到不能用
因为 fib(n) 会重复计算大量子问题，比如 fib(5) 调用时，fib(3) 被算两次，fib(2) 被算三次——时间复杂度是指数级 O(2^n)，n 刚过 40 就明显卡顿。
- 别在生产代码里直接写裸递归，哪怕只是练手也该意识到它不可扩展
- 加个
std::map或数组缓存结果（记忆化）能降到O(n)，但额外占空间，且递归调用栈深度仍可能爆栈（n > 10000 时常见） - 如果非要递归，至少用尾递归形式（C++17 不保证优化，别依赖）
用 for 循环递推才是默认选择
从底向上迭代，只存前两个值，空间 O(1)、时间 O(n)，无栈溢出风险，编译器也容易优化。
- 注意初始边界：n=0 返回 0，n=1 返回 1；有些题目定义从 1,1 开始，得看题干
- 用
long long防止 int 溢出——fib(47)就超int最大值了 - 如果需要多次查不同 n 的值，可预计算打表（比如
std::array<long long></long>，因为fib(94)是long long能存下的最大斐波那契数）
long long fib(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;
}
模板元编程编译期算斐波那契？真没必要
用 constexpr 函数或模板递归确实能在编译期展开，但仅适用于 n 很小（n ）、且确定在编译期就知道值的场景，比如数组长度。
-
constexpr版本运行时也能调，但递归深度受编译器限制（GCC 默认约 512 层），不是通用解法 - 模板特化写法冗长，报错信息难读，调试成本高
- 现代 C++ 更推荐用
constexpr+ 迭代逻辑，而非模板递归
遇到大数（n > 1000）怎么办
标准整型撑不住，得换任意精度整数。但别自己造轮子——boost::multiprecision::cpp_int 或 __int128（GCC/Clang 支持）更靠谱。
立即学习“C++免费学习笔记（深入）”；
-
__int128只支持 GCC/Clang，且不能直接用std::cin/std::cout，输入输出得手动拆字节 - 用
cpp_int时注意：运算比原生类型慢一个数量级以上，n=10000 时已明显感知延迟 - 如果真要算超大 n（如 1e6），得上矩阵快速幂或闭式公式（Binet 公式），但浮点误差会让后者在 n>70 后失效
