4. 斐波那契数列：经典递归案例

聊递归，绕不开斐波那契数列。这玩意儿几乎是每个学递归的人都会碰到的第一个案例。我当年刚学C语言时，老师一上来就甩了这段代码，看得我一愣一愣的。

斐波那契数列的定义很简单：

• 第0项是0
• 第1项是1
• 从第2项开始，每一项等于前两项之和

用数学公式写出来就是：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (n ≥ 2)

这个定义本身就是递归的。你想想看，要算F(n)，得先知道F(n-1)和F(n-2)。而F(n-1)又得知道F(n-2)和F(n-3)……一层层往下拆，直到拆到F(0)和F(1)这两个已知的边界值。

所以用递归实现，几乎是顺理成章的事。

4.1 递归实现：代码很简洁，但问题很大

直接看代码：

#include <stdio.h>

// 递归求斐波那契数列第n项
int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int n = 10;
    printf("fib(%d) = %d\n", n, fib(n));
    return 0;
}

这段代码，说实话，漂亮得很。逻辑清晰，结构对称，完全照着数学定义翻译过来的。你给一个刚学编程的人看，他也能看懂。

但问题来了——你试试把n改成40、50，看看程序跑多久。

我当年在课堂上试过n=45，结果等了快半分钟才出结果。当时我还以为是电脑坏了，后来一分析才发现，这玩意儿的时间复杂度是指数级的。

4.2 指数级时间复杂度：到底有多慢？

为什么会这么慢？我们来分析一下递归调用的过程。

假设你要算fib(5)，调用关系是这样的：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) → 1
│   │   │   └── fib(0) → 0
│   │   └── fib(1) → 1
│   └── fib(2)
│       ├── fib(1) → 1
│       └── fib(0) → 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) → 1
    │   └── fib(0) → 0
    └── fib(1) → 1

你看，光是算fib(5)，fib(2)就被算了3次，fib(1)被算了5次，fib(0)被算了3次。这还只是n=5的情况。n越大，重复计算的次数就越夸张。

我们来算一下时间复杂度。每次调用fib(n)，都会产生两个子调用fib(n-1)和fib(n-2)。这就像一棵二叉树，每个节点分叉成两个子节点。树的深度大约是n，所以总的节点数大约是2ⁿ级别。

严格来说，斐波那契递归的时间复杂度是O(2ⁿ)。

嗯，这里要注意，实际调用次数比2ⁿ略少一些，因为递归树不是满二叉树。但数量级没变，依然是指数级。

4.3 重复计算问题：递归的致命伤

为什么指数级？说白了，就是重复计算太多了。

你看上面的调用树，fib(3)被算了两次，fib(2)被算了三次。每次算fib(3)，它又去递归算fib(2)和fib(1)。这些结果明明之前已经算过了，但递归不会记住它们，每次都得重新算一遍。

我举个例子你就明白了。假设你要算fib(10)，递归过程中fib(5)会被算多少次？答案是——很多次。具体来说，fib(5)会被重复计算89次。你没看错，89次。

为什么会这样？因为fib(10)依赖fib(9)和fib(8)，fib(9)依赖fib(8)和fib(7)，fib(8)依赖fib(7)和fib(6)……每个节点都往下分裂，导致同一个值被反复计算。

4.4 用SVG图看清递归的重复计算

下面这张图展示了fib(6)的递归调用树。你可以清楚地看到，同一个节点被多次计算。

从这张图你能直观地看到，递归树中大量节点是重复的。fib(3)出现了2次，fib(2)出现了3次，fib(1)出现了5次。这些重复计算白白浪费了CPU时间。

4.5 数据说话：n越大，重复越夸张

我整理了一张表，让你看看不同n值下的函数调用次数：

n	函数调用次数	实际计算量	感受
10	177	很少	瞬间出结果
20	21,891	较少	几乎无感
30	2,692,537	百万级	能感觉到延迟
40	331,160,281	3.3亿	等好几秒
50	40,730,022,147	407亿	等到怀疑人生

你看，n从30到40，调用次数从269万跳到3.3亿，增长了120多倍。n从40到50，又从3.3亿跳到407亿，增长了120多倍。这就是指数级增长的恐怖之处。

4.6 小结：递归不是万能的

斐波那契数列的递归实现，是学习递归的经典案例。它展示了递归的优雅——代码简洁、逻辑清晰、与数学定义一一对应。

但它也暴露了递归的致命弱点：重复计算。当问题存在大量重叠子问题时，纯递归会导致指数级的时间复杂度，性能惨不忍睹。

我个人习惯是：遇到递归定义的问题，先写递归版本验证逻辑，然后再考虑优化。如果发现重复计算严重，就改用动态规划或记忆化递归。这个思路在我多年的项目实践中屡试不爽。

下一节，我会讲如何用记忆化递归和动态规划来解决这个重复计算问题。到时候你会发现，同样的功能，性能可以提升几个数量级。

---

公众号:蓝海资料掘金营，微信deep3321