斐波那契数列大概是每个学编程的人最先接触的算法题之一：第一项和第二项为 1，从第三项开始每一项等于前两项之和。问题看似简单，但当你真正去实现求第 n 项时，会发现不同的写法性能差异惊人。同样是计算第 50 项，递归写法可能要跑几秒，迭代法几乎瞬间完成，而矩阵快速幂则能在对数时间内解决超大 n 的问题。本文将用 C++ 分别实现这三种方案，并逐一分析它们的原理、复杂度和适用场景。
一、递归实现：最直观但最慢的写法
递归写法几乎是照搬数学定义，代码非常短，可读性极强。这也是它常被用作教学示例的原因：函数直接表达了 f(n) = f(n-1) + f(n-2) 这一定义。
#include <iostream>
// 递归求斐波那契数列第 n 项（n 从 1 开始）
long long fibRecursive(int n) {
if (n <= 2) return 1;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
int main() {
int n = 40;
std::cout << "fib(" << n << ") = " << fibRecursive(n) << std::endl;
return 0;
}</code>这段代码的问题在于大量的重复计算。以计算 f(5) 为例，它会先算 f(4)，而 f(4) 内部又需要 f(3)；接着算 f(3) 时，f(3) 又被完整地重新计算了一遍。随着 n 增大，重复计算的规模呈指数级膨胀，整个调用树的节点数约为 O(1.618^n)。实测中，n = 40 时现代电脑通常需要一两秒，n = 50 则可能需要几分钟，基本不可用。
递归法的时间复杂度是指数级 O(2^n)（更精确地说是 O(φ^n)，φ 为黄金分割比），空间复杂度为 O(n)，对应递归调用栈的深度。它只适合教学演示或 n 非常小的场合。如果想保留递归结构又提升性能，可以加一个记忆化数组，把已经算出的结果缓存起来，这样时间复杂度会降为 O(n)，本质上变成了自顶向下的动态规划。
二、迭代实现：线性复杂度的实用方案
既然 f(n) 只依赖前两项，我们完全没必要保存整个数列，用两个变量滚动更新就够了。这种写法消除了递归的函数调用开销，也不会产生重复计算，是最常用的工程实现。
#include <iostream>
// 迭代求斐波那契数列第 n 项
long long fibIterative(int n) {
if (n <= 2) return 1;
long long prev = 1, curr = 1;
for (int i = 3; i <= n; ++i) {
long long next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
int main() {
int n = 80;
std::cout << "fib(" << n << ") = " << fibIterative(n) << std::endl;
return 0;
}迭代法的时间复杂度为 O(n)，空间复杂度为 O(1)，无论 n 多大，内存占用都恒定。在 n 不超过 90 左右时，long long 可以装下结果（f(92) 是 64 位有符号整数能表示的最后一项）。超出这个范围就会发生整型溢出，结果变负数，这是实际编码中最容易踩的坑。
当 n 非常大（比如上亿）或者题目要求对一个大数取模时，O(n) 的迭代可能仍嫌太慢。此外，若结果本身要精确表示（不取模），还需要借助高精度整数库，因为 C++ 内置类型无法表示上百位的数。这类需求正是矩阵快速幂的用武之地。
三、矩阵快速幂：对数级别的最优解
斐波那契递推式可以写成矩阵形式：[f(n), f(n-1)] = [f(n-1), f(n-2)] 乘以转移矩阵 [[1,1],[1,0]]。把这个等式递推下去，就得到 [f(n), f(n-1)] = [[1,1],[1,0]] 的 (n-2) 次幂乘以初始向量。于是求 f(n) 就变成了求一个 2×2 矩阵的 n-2 次方，而快速幂算法利用二分思想，只需 O(log n) 次矩阵乘法即可完成。
#include <iostream>
const long long MOD = 1000000007; // 常用大质数取模，防止溢出
struct Matrix {
long long a[2][2];
};
// 2x2 矩阵相乘（带取模）
Matrix multiply(const Matrix &x, const Matrix &y) {
Matrix res;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j) {
res.a[i][j] = 0;
for (int k = 0; k < 2; ++k)
res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
}
return res;
}
// 矩阵快速幂：求 base 的 exp 次方
Matrix matrixPower(Matrix base, long long exp) {
Matrix result = {{{1, 0}, {0, 1}}}; // 单位矩阵
while (exp > 0) {
if (exp & 1) result = multiply(result, base);
base = multiply(base, base);
exp >>= 1;
}
return result;
}
// 求第 n 项斐波那契数（对 MOD 取模），n 从 1 开始
long long fibMatrix(long long n) {
if (n <= 2) return 1;
Matrix base = {{{1, 1}, {1, 0}}};
Matrix res = matrixPower(base, n - 2);
// 结果为 res 与初始向量 [f(2), f(1)] 相乘后的第一项
return (res.a[0][0] + res.a[0][1]) % MOD;
}
int main() {
long long n = 1000000000; // 十亿
std::cout << "fib(" << n << ") mod 1e9+7 = " << fibMatrix(n) << std::endl;
return 0;
}快速幂的核心逻辑在于指数的二进制分解：每次循环判断指数最低位，如果为 1 就把当前底数乘进结果；随后底数自乘平方，指数右移一位。由于指数的二进制位数只有 log n 个，整个循环至多执行 log n 次，每次做常数次 2×2 矩阵乘法，总时间复杂度为 O(log n)。即使 n 取到十亿甚至更大，也只需约 30 次矩阵乘法即可得到答案。
注意代码中所有乘法都带上了取模操作。因为两个不超过 MOD 的数相乘最大约 10^18，恰好还在 long long 的表示范围内，所以先取模再相乘是安全的。如果不取模，中间结果会迅速溢出。这也是竞赛和在线测评题目中处理大数斐波那契的标准做法。除了矩阵快速幂，还有基于通项公式变形的「斐波那契恒等式」加速方法，同样能达到 O(log n)，不过矩阵写法思路更通用，可以推广到所有线性递推数列。
四、三种方案对比与选型建议
把三种实现放在一起对比，差距一目了然：
| 实现方式 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素递归 | O(2^n) | O(n) | 教学演示，n 较小 |
| 迭代 | O(n) | O(1) | 日常开发，n 在 90 以内 |
| 矩阵快速幂 | O(log n) | O(1) | 超大 n 且对大数取模 |
实际选型时可以遵循这样的思路：如果只是学习递归思想，用朴素递归即可，但务必清楚它的指数级代价；如果是一般业务代码，迭代法简单可靠，是最稳妥的选择；如果 n 达到百万级以上，或者题目明确要求对 10^9+7 这类大数取模，就应该上矩阵快速幂。
最后补充一个常见的优化方向：在递归版本上加记忆化（用 unordered_map 或数组缓存已计算的结果），可以把复杂度降到 O(n)，这种写法兼具递归的清晰结构和接近迭代的效率，也是理解动态规划「自顶向下」思路的好例子。无论选择哪种方案，都别忘了确认结果是否会超出 long long 的范围，必要时取模或使用高精度运算，这是斐波那契数列题目中最容易出错的地方。