21、递归函数的陷阱：斐波那契数列为什么那么慢？
斐波那契数列，几乎是每个学编程的人都会遇到的经典例子。教科书上总喜欢用递归来实现，代码确实简洁优雅。但如果你真的在项目里这么写，嗯，我敢打赌你会被领导叫去喝茶。
今天我们就来聊聊，这个看似完美的递归实现，到底慢在哪里？
先看代码：教科书式的递归实现
// 计算第 n 个斐波那契数
int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}这段代码，我估计你见过不下十次。逻辑清晰，代码短小，递归的「自我调用」特性展现得淋漓尽致。但问题来了——你试过用这个函数算 fib(50) 吗？
我试过。等了几分钟没出结果，最后直接按了 Ctrl+C。为什么会这样？
递归的「重复计算」陷阱
我们画个调用图看看。假设你要算 fib(5)：
看到了吗？fib(3) 被算了两次，fib(2) 被算了三次，fib(1) 和 fib(0) 更是被反复计算。这还只是 n=5 的情况。当 n 变大时，重复计算的次数呈指数级增长。
核心问题：递归斐波那契的时间复杂度是 O(2ⁿ)，而不是 O(n)。n=50 时，函数调用次数超过 2⁵⁰ ≈ 1.1259×10¹⁵ 次。就算你的 CPU 每秒能执行 10⁹ 次函数调用，也要算上 12 天多。
为什么递归会这么「蠢」？
说白了，递归函数没有「记忆」。它每次调用都从零开始算，完全不记得之前算过什么。你想想看，fib(3) 的结果明明已经算出来过一次，但递归不会把它存下来，下次需要时又得重新算一遍。
我在项目中遇到过类似的问题。有一次做嵌入式设备的参数配置解析，用了递归去遍历嵌套的配置结构体。结果设备启动时卡了将近 10 秒才完成初始化。后来一查，就是递归重复解析了相同的配置段。嗯，从那以后我对递归就多留了个心眼。
怎么解决？两种主流方案
方案一：记忆化递归（Memoization）
给递归加个「备忘录」。算过的结果存起来，下次直接用。
#include <stdio.h>
#include <string.h>
#define MAX_N 1000
long long memo[MAX_N + 1];
long long fib_memo(int n) {
if (n <= 1) {
return n;
}
// 如果已经算过，直接返回
if (memo[n] != -1) {
return memo[n];
}
// 没算过，算一次并记录
memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
return memo[n];
}
int main() {
memset(memo, -1, sizeof(memo));
printf("fib(50) = %lld\n", fib_memo(50));
return 0;
}这个版本的时间复杂度降到了 O(n)。算 fib(50) 几乎是瞬间完成。每个 n 只算一次，后面全是查表。
小提示：记忆化递归本质上是用空间换时间。memo 数组的大小要提前规划好，别越界。我在嵌入式项目里一般用静态数组，动态分配在资源受限的环境下容易出问题。
方案二：迭代法（循环）
既然递归有这么多坑，为什么不直接用循环？
long long fib_iter(int n) {
if (n <= 1) {
return n;
}
long long a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}这个版本更直接。没有函数调用开销，没有栈溢出风险，时间复杂度 O(n)，空间复杂度 O(1)。
我个人习惯在嵌入式开发中优先用迭代法。原因很简单——嵌入式设备的栈空间通常很有限，递归深度稍微大一点就可能栈溢出。我曾经在一个 RTOS 任务里用递归，结果任务栈设了 512 字节都不够用，最后改成迭代才搞定。
递归 vs 迭代：什么时候该用递归？
| 对比维度 | 递归 | 迭代 |
|---|---|---|
| 代码可读性 | 简洁，符合数学定义 | 稍显啰嗦 |
| 时间复杂度 | O(2ⁿ)（朴素递归） | O(n) |
| 空间复杂度 | O(n)（调用栈） | O(1) |
| 栈溢出风险 | 高（深度大时） | 无 |
| 适用场景 | 树遍历、分治算法 | 线性计算、循环处理 |
递归不是不能用，但要选对场景。像斐波那契这种线性递推的问题，用迭代明显更合适。而像遍历二叉树、快速排序这种天然具有递归结构的问题，用递归反而更自然。
避坑指南：我曾经在嵌入式设备上用递归实现一个 JSON 解析器，嵌套深度超过 100 层时直接导致系统复位。后来改成迭代 + 显式栈管理，问题才解决。记住：递归深度超过 50 层就要警惕了，超过 100 层基本是定时炸弹。
总结一下
斐波那契数列的递归实现之所以慢，根本原因在于重复计算。每次递归调用都重新计算子问题，导致时间复杂度爆炸到 O(2ⁿ)。
解决方案有两个方向：
- 记忆化递归：用数组缓存结果，空间换时间，复杂度降到 O(n)。
- 迭代法：彻底抛弃递归，用循环实现，性能最优。
在实际项目中，我建议你优先考虑迭代。如果非要用递归，一定要评估好递归深度，必要时加上记忆化优化。别让递归成为你程序里的「性能黑洞」。
嗯，今天就聊到这里。下次写递归之前，先想想——这个函数真的需要递归吗？
公众号:蓝海资料掘金营，微信deep3321