c++中如何实现斐波那契数列_c++递归、迭代与矩阵快速幂【详解】

递归实现斐波那契在C++中易栈溢出，因重复计算导致O(2^n)时间复杂度且深度递归压栈；n>100时极易溢出，尾递归优化不保证生效；应改用迭代，用unsigned long long并校验n≤93。

c++中如何实现斐波那契数列_c++递归、迭代与矩阵快速幂【详解】第1张

为什么递归实现 `fibonacci` 在 C++ 中容易栈溢出

因为未经优化的递归版本会重复计算大量子问题，比如 fib(5) 会两次调用 fib(3)，时间复杂度是 O(2^n)。更关键的是，每次函数调用都压栈，n 超过 100 就大概率触发栈溢出（尤其在默认栈大小下）。编译器对尾递归的优化在 C++ 中不保证生效，所以不能依赖。

实操建议：

绝对不要在生产代码中用裸递归算 fib(n)，哪怕加了 if (n
若真要用递归，必须加记忆化（memoization），用 std::unordered_map 或数组缓存已算结果
调试时可设断点观察调用深度，n == 40 时递归深度就已超 40 层

迭代法写 `fibonacci` 怎么避免整数溢出和边界错误

迭代最安全，时间 O(n)、空间 O(1)，但两个常见坑：一是没处理 n == 0 和 n == 1 的初始值，二是用 int 存结果导致第 47 项就溢出（fib(47) = 2971215073 > INT_MAX）。

实操建议：

统一用 unsigned long long，能撑到 fib(93)
循环从 i = 2 开始，初始化 a = 0, b = 1，每次更新为 std::make_pair(b, a + b)
对输入做校验：if (n > 93) throw std::overflow_error("fibonacci overflow");

unsigned long long fib_iter(int n) {
    if (n < 0) throw std::invalid_argument("n must be non-negative");
    if (n == 0) return 0;
    if (n == 1) return 1;
    unsigned long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        unsigned long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}