c++如何实现斐波那契数列_c++递归与递推解法【入门】

递归写法因重复计算导致时间复杂度达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 后失效

实际写的时候，先问自己：n 多大？是否频繁调用？是否必须编译期？答案一出来，路径就清楚了。边界和溢出不是“可能出问题”，是“一定会出”。