CC++ & Algorithm

C++递归优化策略

较难11
语言版本：C++Python
概述：用“借书记录单”的比喻，教你如何给递归程序“减负”，避免重复计算，让程序跑得更快。

递归跑得慢？给它配一张“借书记录单”！

你有没有遇到过这样的烦恼：写了一个递归程序，明明思路很清晰，可运行起来却像老牛拉破车，算个不大的数都要等上好几秒？别急，这不是你的程序有错，而是递归有个“健忘症”——它总把算过的结果忘掉，一次又一次地重算，白白浪费了时间。

今天我们就来学一个超实用的技巧：记忆化（Memoization），就像给递归配上一张“借书记录单”，让它记住算过的结果，再也不会重复劳动，速度一下子飞起来！

1. 递归的“健忘症”——重复计算

先看看递归是怎么犯“健忘症”的。假设我们写一个求斐波那契数列的函数 fib(n)，定义是：

  • fib(0) = 0，fib(1) = 1
  • fib(n) = fib(n-1) + fib(n-2)

用递归写出来就是：

#include <iostream>
using namespace std;

int fib(int n) {
    if (n <= 1) return n;          // 第0项是0，第1项是1
    return fib(n-1) + fib(n-2);    // 自己调自己
}

这个代码看起来很简单，但跑起来就“露馅”了。我们来数一数当 n=5 时，fib(3) 会被调用几次？
调用图大概是这样：

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) 被算了 2 次，fib(2) 被算了 3 次，fib(1) 被算了 5 次！这就像你去图书馆借书，第一次查到了《哈利波特》在第3排第2格，结果下次你又要借同一本书，却忘了它在哪，从头把整个图书馆找一遍。写作业时，老师让你算1加到100，你算完1+2+3+...+50，过一会儿又让你算1+2+3+...+50，你难道要重新加一遍？多累呀！

这种重复计算就是递归效率低下的主要原因，尤其是当 n 变大时（比如 n=40），计算量会爆炸式增长，你的电脑可能卡住好几秒才算出来。

2. 给递归戴上“备忘录”——记忆化搜索

怎么解决呢？很简单：把算过的结果记下来，下次再要的时候，直接掏出来用，不用再算一遍。

就像你去图书馆借书，带一张“借书记录单”：

  • 第一次查到“《哈利波特》在第3排”，你写在单子上：书：哈利波特 → 位置：第3排
  • 下次再借这本书，你先翻记录单，哦，在第3排，直接去拿！

在程序里，我们用一个数组（或者别的容器）当“记录单”。数组的每个位置对应一个 n，存放已经算好的结果。初始时，我们给每个位置放一个“还没算过”的标记（比如 -1），一旦算过，就把结果存进去。

改造前的代码（未优化）

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 每次都要重新算
}

改造后的代码（记忆化）

#include <iostream>
using namespace std;

const int MAX = 100;          // 假设最多算到100项
int memo[MAX];                // 记录单数组，每个元素存fib(n)的结果

// 初始化函数：把所有记录设为 -1（表示还没算过）
void initMemo() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }
}

int fib(int n) {
    if (n <= 1) return n;                // 边界情况：fib(0)=0, fib(1)=1
    if (memo[n] != -1) return memo[n];    // 如果记录单上已经有结果，直接拿
    // 否则，算一遍，存进记录单
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

int main() {
    initMemo();                // 在使用前先初始化记录单
    cout << "fib(50) = " << fib(50) << endl;
    return 0;
}

注意这里的细节： 为什么用 -1 而不是 0 来初始化？
因为 fib(0) = 0，如果初始值用 0，那么 memo[0] 是 0，程序会误以为已经算过了，直接返回 0 没错，但 memo[其他] 如果也是 0，就会出错。比如 fib(2) = 1，结果还没算时 memo[2]=0，程序误以为 fib(2)=0 就返回错了。所以我们要用一个不可能出现的值（比如 -1）来表示“还没算”。

优化之后，每个 fib(n) 只会被真正计算一次，后面的调用直接查表。原来算 fib(40) 可能要等好几秒，现在瞬间出结果，连眨眼都不需要！

3. 再举一个例子：爬楼梯问题

小明爬楼梯，每次可以走1级或2级台阶。请问到第10级台阶有多少种不同的走法？

这个问题也可以用递归想：

  • 走到第 n 级台阶的走法 = 走到第 n-1 级的走法 + 走到第 n-2 级的走法（因为最后一步要么跨1级，要么跨2级）。
  • 边界：走到第0级只有1种走法（不动），走到第1级只有1种走法（跨1级）。

如果不优化，直接写递归：

int climbStairs(int n) {
    if (n <= 1) return 1;          // 到第0级或第1级都只有1种
    return climbStairs(n-1) + climbStairs(n-2);  // 重复计算严重
}

同样的问题：n=40 时，重复计算的次数多到让你怀疑人生。

用记忆化优化：

#include <iostream>
using namespace std;

const int MAX = 100;          // 最多算到100级
int memo[MAX];                // 记录单

void initMemo() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }
}

int climbStairs(int n) {
    if (n <= 1) return 1;                // 边界
    if (memo[n] != -1) return memo[n];    // 查记录单
    memo[n] = climbStairs(n-1) + climbStairs(n-2); // 算一次存下来
    return memo[n];
}

int main() {
    initMemo();
    cout << "到第10级台阶有 " << climbStairs(10) << " 种走法" << endl; // 输出89
    cout << "到第40级台阶有 " << climbStairs(40) << " 种走法" << endl; // 很快出结果
    return 0;
}

你看，加上“记录单”后，原本算 n=40 可能要十几秒的程序，现在跑得飞快！就像你写作业时，把算过的题目答案记在小本子上，后面遇到类似的直接抄，省时又省力。

4. 新手常见错误

刚开始用记忆化时，容易掉进这些坑里，看看你踩过几个？

错误1：用0初始化记录单

int memo[100] = {0};  // 全部初始化为0
// 然后判断 if (memo[n] != 0) ...

后果： 如果 fib(0) = 0 是正确结果，那么 memo[0] 永远为0，程序会以为它还没算过，导致递归进入死循环？其实不会死循环，但会重复计算 fib(0) 很多次，浪费一点时间。更严重的是，如果某个中间结果恰好也是0（比如 fib(2)=1 不会为0，但其他递归可能产生0结果），就会误判为没算过，导致重复计算或逻辑错误。解决方法： 用一个不可能出现的值（如 -1）初始化，或单独开一个布尔数组记录是否算过。

错误2：忘记初始化记录单

int memo[MAX];  // 没有初始化，里面是垃圾值

后果： 随机判断 if (memo[n] != -1)，可能永远不成立，也可能意外成立，导致结果错误或程序崩溃。一定要在使用前把记录单全部设成同一个标记值。

错误3：记录单大小不够

const int MAX = 10;  // 结果你要算 fib(50)

后果： 数组越界，程序可能崩溃或输出奇怪的值。根据问题规模设置足够大的数组（比如 1000 或更多），或者用动态数组（vector）。

错误4：边界条件写错

比如爬楼梯问题，n <= 1 返回 1，有人写成 n == 1 返回 1，忘记处理 n=0 的情况，导致递归一直减到负数才停。仔细检查边界。

5. 完整可运行示例：斐波那契 + 爬楼梯

下面是一个完整的程序，包含了两个记忆化递归函数，你可以直接复制到编译器里运行，感受一下速度差异。

#include <iostream>
using namespace std;

const int MAX = 1000;        // 数组最大容量

// ---------- 斐波那契 ----------
int fibMemo[MAX];            // 斐波那契的记录单

void initFib() {
    for (int i = 0; i < MAX; i++) {
        fibMemo[i] = -1;     // -1表示还没算
    }
}

int fib(int n) {
    if (n <= 1) return n;               // 边界：fib(0)=0, fib(1)=1
    if (fibMemo[n] != -1) return fibMemo[n]; // 查记录单
    fibMemo[n] = fib(n-1) + fib(n-2);   // 算一次，存起来
    return fibMemo[n];
}

// ---------- 爬楼梯 ----------
int climbMemo[MAX];          // 爬楼梯的记录单

void initClimb() {
    for (int i = 0; i < MAX; i++) {
        climbMemo[i] = -1;
    }
}

int climbStairs(int n) {
    if (n <= 1) return 1;               // 到第0或第1级都是1种
    if (climbMemo[n] != -1) return climbMemo[n];
    climbMemo[n] = climbStairs(n-1) + climbStairs(n-2);
    return climbMemo[n];
}

int main() {
    initFib();
    initClimb();

    cout << "=== 记忆化递归演示 ===" << endl;
    cout << "fib(50) = " << fib(50) << endl;              // 瞬间出结果
    cout << "爬楼梯到第40级: " << climbStairs(40) << " 种走法" << endl;

    // 你可以试试去掉记忆化的版本，算 fib(40) 就很慢
    return 0;
}

运行结果（会很快显示）：

=== 记忆化递归演示 ===
fib(50) = 12586269025
爬楼梯到第40级: 165580141 种走法

对比一下，如果去掉记忆化，算 fib(40) 可能就要好几秒，更别说 fib(50) 了。

6. 相关指引

记忆化递归是动态规划（Dynamic Programming, DP）的亲戚，你可以认为记忆化就是“自顶向下的动态规划”。动态规划还有另一种写法叫“自底向上”，直接用循环从小的 n 开始递推，不需要递归，用数组存结果，速度更快也更省空间。

想要继续学习？

  • 试试用记忆化解决“数塔问题”“走迷宫”等题目。
  • 搜索“C++ 动态规划入门”，了解更多优化技巧。
  • 如果觉得递归很慢，还可以把递归改成迭代（循环），比如斐波那契可以直接用 for 循环从第2项算到第n项，既简单又高效。

递归虽然好用，但别忘了给它带上“备忘录”——记忆化，这样你的程序才能跑得又快又好！快去给你的递归程序配一张“借书记录单”吧！

例题精讲

1单选题

以下哪个是C++编译器进行尾递归优化的必要条件？

A递归调用是函数的最后一条语句
B递归调用不占用栈空间
C递归调用必须返回void
D递归调用不能有参数
2判断题

使用记忆化优化递归时，所有递归函数都可以通过添加缓存数组来获得性能提升。

3填空题
完成记忆化斐波那契函数：
int fib(int n, int memo[]) {
  if (n <= 1) return n;
  if (memo[n] != -1) return ___;
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return ___;
}