5. 递归优化之记忆化：用数组/哈希表缓存中间结果

聊到递归优化，我得先跟你掏心窝子说一句：纯递归的斐波那契，是教学用的反面教材。

你想想看，一个 fib(40) 跑下去，你的电脑风扇就开始转了。为什么？因为它在疯狂重复计算。我当年刚学递归时，也写过这种代码，还傻乎乎地等它跑完——等了快一分钟。后来我才明白，这叫「指数级爆炸」。

5.1 问题出在哪？

先看这段代码：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

漂亮，简洁，但致命。

画个调用树你就懂了：

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

看到了吗？fib(3) 算了两次，fib(2) 算了三次。n 越大，重复越严重。时间复杂度是 O(2ⁿ)——n=50 时，调用次数超过 10¹⁵，这辈子都跑不完。

5.2 记忆化：用空间换时间

解决方案其实很朴素：算过的结果，存起来。

我习惯用一个数组来缓存。每次递归前先查表，有就直接返回，没有才去算。

#include <stdio.h>
#include <string.h>

#define MAX 1000

int memo[MAX];

int 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) = %d\n", fib_memo(50));
    return 0;
}

这里我用 -1 表示「还没算过」。因为斐波那契值都是非负整数，-1 是个安全的标记值。

5.3 复杂度对比

方法	时间复杂度	空间复杂度	n=50 调用次数
纯递归	O(2ⁿ)	O(n)	≈ 2×10¹⁰
记忆化递归	O(n)	O(n)	51 次

从指数级降到线性级，这就是记忆化的威力。

5.4 核心逻辑流程图

下面这张图帮你理清记忆化递归的执行路径：

5.5 避坑指南

另外，注意递归深度。n=10000 时，即使有记忆化，递归调用栈也可能溢出。这时候我建议改用迭代，或者手动模拟栈。不过那是另一节课的内容了。

5.6 什么时候用记忆化？

• 有重叠子问题：同一个子问题被多次调用
• 最优子结构：子问题的最优解能推导出原问题的最优解
• 状态空间有限：n 的范围可控，缓存放得下

说白了，只要你的递归树里有「重复的枝桠」，记忆化就能派上用场。动态规划里几乎所有的「自顶向下」解法，本质就是记忆化递归。

---

好了，这一节就到这里。代码不多，但思想很重要。下次你写递归时，试试先画个调用树，看看有没有重复计算。如果有，记忆化就是你的第一把刀。