c++如何实现斐波那契数列_c++递归与非递归写法【算法】

递归写法简洁但易栈溢出；需设边界n

递归写法：简洁但容易栈溢出

直接用 fib(n) = fib(n-1) + fib(n-2) 定义，边界是 n 时返回 n。看似直观，但时间复杂度是指数级 O(2^n)，因为重复计算大量子问题。

常见错误现象：fib(50) 就明显卡顿，fib(100) 基本无法在合理时间内返回；调用深度过大还会触发栈溢出（stack overflow）。

实操建议：

• 仅用于教学演示或 n 的极小规模场景
• 加个简单剪枝（如记忆化）就能大幅改善，但那就不是纯递归了
• 别在生产代码里裸写这个版本，尤其不能放在实时或嵌入式环境中

迭代写法：推荐的默认实现

用两个变量 a 和 b 滚动更新，每次算出下一个值后平移窗口。时间复杂度 O(n)，空间复杂度 O(1)，稳定、高效、无栈风险。

典型使用场景：需要快速获取第 n 项、批量生成前 N 项、内存受限环境（如单片机）。

注意点：

• n = 0 和 n = 1 要单独处理，避免循环不执行就返回错误值
• 如果 n 很大（比如 > 90），int 或 long long 会溢出，得用 unsigned long long 或大数库
• 循环起始条件别写成 i = 2; i ，而应是 i = 2; i ，否则多算一轮

矩阵快速幂：适合超大 n 的对数解法

利用斐波那契的线性递推可表示为矩阵乘法：[f(n), f(n-1)]^T = [[1,1],[1,0]]^(n-1) * [f(1), f(0)]^T。用快速幂把乘方降到 O(log n) 时间。

适用条件：

• n 达到 1e18 级别，迭代都嫌慢
• 题目明确要求“模某个数”（如 1e9+7），此时矩阵元素可全程取模
• 你熟悉二进制拆分和矩阵乘法封装

坑点：

• 单位矩阵初始化错（比如设* 0）会导致结果恒为 0
• 幂次是 n-1 而不是 n，n=0 和 n=1 必须特判
• 手写 2×2 矩阵乘法时行列顺序写反，结果完全不对

模板类封装：兼顾类型安全与复用性

用 template 包一层迭代逻辑，既能支持 int、long long，也能配合自定义大整数类型使用。比裸函数更健壮。

示例核心片段：

template
T fib(int n) {
    if (n <= 1) return static_cast(n);
    T a = 0, b = 1;
    for (int i = 2; i < n; ++i) {
        T c = a + b;
        a = b;
        b = c;
    }
    return b;
}

关键细节：

• 强制转换 static_cast(n) 防止 n 是负数或大整数时隐式截断
• 不要用

  

  auto 推导 a/b 类型——它会绑定到参数 n 的类型，而非模板参数 T
• 若需支持编译期计算（constexpr），得改用 constexpr 迭代或特化，普通 for 循环不行

实际项目中，95% 的情况用迭代就够了。矩阵快速幂看着炫，但多数业务场景根本不需要那么大的 n；而递归除了讲原理，基本没有上生产的价值。类型封装倒值得花十分钟写好，以后所有数值类型都能复用。