递归：让函数自己调用自己的魔法思维

你有没有玩过这样一种游戏？一面镜子里照出另一面镜子，里面又有一个更小的镜子……永远看不到头。或者像俄罗斯套娃，打开一个娃娃，里面藏着一个更小的，再打开，还有更小的，直到最后一个最小的小人。递归（Recursion） 就是程序世界里的“套娃”——一个函数在执行的过程中，调用它自己。

递归特别适合解决那种“大问题可以拆成小问题，小问题和原问题解法一样”的情况。比如：数一堆积木有多少块，如果你每次只拿一块，最后慢慢数，很慢。但如果你把积木分成两堆，数左边再数右边，每堆如果还多继续分，直到每堆只剩一块，这就用上了递归的思路——大事化小，小事化了。

今天我们就来认识这个神奇的概念，看看它怎么用在C++里帮你写出简洁又聪明的代码。

一、递归的两个关键：基本情形 + 递归步骤

任何一个递归函数，都像一道数学题：题目要求你从“大”开始，逐步退到“小”，直到遇到一个直接可以回答的问题。这个直接可以回答的问题，就是基本情形（base case），也叫递归出口。而不断拆分问题的步骤，叫做递归步骤（recursive step）。

生活中理解递归：排队传话

想象一下，你排在一个很长的队伍里，想知道队伍一共有多少人。你可以：

1. 问你前面的那个人：“他前面还有几个人？”
2. 他再问他前面的那个人……
3. 直到排在最前面的那个人，他前面没有人了，他就回答“0”。
4. 然后消息一个一个传回来：第一个人答0，第二个人听到后回答1，第三个人回答2……最后传到你这里，你就知道整个队伍的人数了。

这个过程中，“最前面那个人”就是基本情形（知道答案是0），而“问他前面的人”就是递归步骤（把问题缩小）。

C++中的例子：从1加到n

下面这段代码用递归计算从1加到n（1+2+3+...+n）：

#include <iostream>
using namespace std;

// 递归计算 1+2+...+n 的和
int sum(int n) {
    if (n == 1) {               // 基本情形：如果n=1，和就是1，直接返回
        return 1;
    }
    return n + sum(n - 1);      // 递归步骤：把 sum(n) 拆成 n + sum(n-1)
}

int main() {
    cout << sum(5) << endl;     // 输出 1+2+3+4+5 = 15
    return 0;
}

这个函数怎么工作？

• 当你调用 sum(5) 时，它发现 n=5，不等于1，所以执行 return 5 + sum(4)。
• 但是还不能直接算出结果，因为 sum(4) 还没算完，于是先记住“我要等 sum(4) 的结果，然后加上5”。
• 然后去算 sum(4)，它又会去找 sum(3)……
• 直到 sum(1)，n=1，满足基本情形，直接返回1。
• 然后一层一层返回结果：sum(1)=1 → sum(2)=2+1=3 → sum(3)=3+3=6 → sum(4)=4+6=10 → sum(5)=5+10=15。

注意：如果递归没有基本情形，比如下面这个，就会变成 无限递归，最终程序崩溃：

// ❌ 错误例子：没有基本情形
int bad_sum(int n) {
    return n + bad_sum(n - 1);  // 永远停不下来，直到栈溢出
}

二、递归的调用过程：就是一本“备忘录叠叠乐”

为了真正理解递归是怎么执行的，我们需要了解计算机里一个叫 栈（stack） 的结构。栈就像一叠盘子，你只能从最上面放盘子，也只能从最上面拿盘子（后进先出）。每一次函数调用，计算机会把当前函数的状态（参数、局部变量、返回地址等）压入栈中，等函数返回时再弹出。

例子：计算阶乘（n! = n×(n-1)×...×1）

先看代码：

#include <iostream>
using namespace std;

// 递归计算 n 的阶乘
int fact(int n) {
    if (n == 0) return 1;           // 基本情形：0! = 1
    return n * fact(n - 1);         // 递归步骤：n! = n * (n-1)!
}

int main() {
    cout << fact(3) << endl;        // 3! = 6
    return 0;
}

当运行 fact(3) 时，栈里面的变化就像一本不断加厚的备忘录：

1. 程序开始 调用 fact(3)：n=3，不满足n==0，所以执行 return 3 * fact(2)。但此时不能马上算出结果，因为需要先知道 fact(2) 的值。于是计算机把“当前状态——n=3，等待 fact(2)的结果”压入栈（用括号表示栈帧）。

2. 调用 fact(2)：n=2，执行 return 2 * fact(1)。又把“n=2”压栈。

3. 调用 fact(1)：n=1，执行 return 1 * fact(0)。压入“n=1”。

4. 调用 fact(0)：n=0，满足n==0，直接返回1。此时栈顶是上一层的 fact(1)，它收到了 fact(0)返回的1。
   弹出 fact(0)，栈顶变为 fact(1)。

5. fact(1)继续：计算 1 * 1 = 1，返回1给 fact(2)。弹出 fact(1)。

6. fact(2)继续：计算 2 * 1 = 2，返回2给 fact(3)。弹出 fact(2)。

7. fact(3)继续：计算 3 * 2 = 6，返回6给 main()。弹出 fact(3)。最终输出6。

整个过程可以想象成传话：你问第一个人“3!等于多少？”，他说“等我去问第二个人”，第二个人又说“等我去问第三个人”……直到最后一个人（fact(0)）直接回答“1”，然后消息倒着传回来。这就是递归的 递推（调用） 和 回归（返回） 两个阶段。

记住：栈的大小有限

如果递归层数太多（比如 fact(10000)），栈会占满内存，导致 栈溢出（stack overflow），程序崩溃。这就是为什么递归不能无限制使用。

三、新手最容易犯的错误

错误1：忘记写基本情形，或者基本情形不对

// ❌ 没有基本情形，永远递归
int sum_wrong(int n) {
    return n + sum_wrong(n - 1);
}

这样调用 sum_wrong(5) 会一直往下减：5→4→3→2→1→0→-1→-2……永远不停止，最终栈溢出。

修正：加上基本情形，比如 if (n == 1) return 1;

错误2：递归步骤没有让问题规模缩小

// ❌ 参数越变越大，永远到不了基本情形
int loop_forever(int n) {
    if (n == 0) return 0;
    return n + loop_forever(n + 1);  // n 变成 n+1，越来越大
}

修正：确保每次递归调用时参数越来越接近基本情形（比如 n-1 或 n/2）。

错误3：返回值类型或逻辑错误

比如计算斐波那契数列时，忘记了前两项的关系。我们会在后面详细讲。

四、递归的优化：避免重复计算和栈溢出

递归虽然简洁，但有时效率很低，甚至卡死。最经典的就是 斐波那契数列（每个数等于前两个数之和：0, 1, 1, 2, 3, 5, 8, ...）。

普通递归——慢吞吞的蜗牛

#include <iostream>
using namespace std;

// 递归计算斐波那契数列第 n 项（慢版本）
int fib(int n) {
    if (n <= 1) return n;          // 基本情形：fib(0)=0, fib(1)=1
    return fib(n-1) + fib(n-2);    // 递归：fib(n) = fib(n-1) + fib(n-2)
}

int main() {
    cout << fib(40) << endl;       // 计算很慢，可能要等几秒
    return 0;
}

为什么慢？ 因为有很多重复计算。比如算 fib(5) 时，需要算 fib(4) 和 fib(3)，而算 fib(4) 又需要算 fib(3) 和 fib(2)，fib(3) 被算了两次。数字越大，重复越多，就像在图书馆里每次找同一本书都从头翻起，浪费大量时间。

优化一：记忆化搜索（加备忘录）

把已经算过的结果存下来，下次直接拿来用，不再重复算。

#include <iostream>
using namespace std;

const int MAX = 100;
long long memo[MAX] = {0}; // 备忘录数组，初始全为0，表示还没算过

// 带备忘录的斐波那契（快版本）
long long fib(int n) {
    if (n <= 1) return n;                // 基本情形
    if (memo[n] != 0) return memo[n];     // 如果已经算过，直接返回
    memo[n] = fib(n-1) + fib(n-2);        // 计算并存入备忘录
    return memo[n];
}

int main() {
    cout << fib(100) << endl; // 瞬间出结果，不会重复计算
    return 0;
}

这就像你做练习册时把做过的难题答案记在笔记本上，下次遇到同样的题直接抄答案，不用重新算一遍。

优化二：改为循环迭代（不用递归）

用循环完全可以避免递归和栈溢出，而且速度更快。

#include <iostream>
using namespace std;

// 循环计算斐波那契数列第 n 项（迭代版本）
long long fib(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, c; // a是前两个数中的第一个，b是第二个
    for (int i = 2; i <= n; i++) {
        c = a + b;   // 新的数 = 前两个数之和
        a = b;       // 向前移动
        b = c;
    }
    return b;
}

int main() {
    cout << fib(100) << endl; // 也很快，且不占用栈空间
    return 0;
}

什么时候该用递归，什么时候该用循环？

五、完整示例：用递归画一把尺子（模拟分割）

我们来看一个有趣的应用：用递归打印一个“刻度尺子”，比如在主刻度之间不断添加小刻度。

#include <iostream>
using namespace std;

// 递归函数：在区间 [left, right] 上画刻度，depth 表示当前深度
void drawRuler(int left, int right, int depth) {
    if (depth == 0) return;          // 基本情形：深度到0，不再画

    int mid = (left + right) / 2;    // 中间位置
    cout << "位置 " << mid << " 画深度 " << depth << " 的刻度" << endl;

    drawRuler(left, mid, depth - 1);   // 左半部分继续画，深度减1
    drawRuler(mid, right, depth - 1);  // 右半部分继续画
}

int main() {
    cout << "刻度尺子递归过程：" << endl;
    drawRuler(0, 8, 3); // 在0到8之间，画3个层级的刻度
    return 0;
}

运行结果（示意，实际顺序是深度优先）：

位置 4 画深度 3 的刻度
位置 2 画深度 2 的刻度
位置 1 画深度 1 的刻度
位置 3 画深度 1 的刻度
位置 6 画深度 2 的刻度
位置 5 画深度 1 的刻度
位置 7 画深度 1 的刻度

这个程序展示了递归如何把一个大区间不断二分，每次先处理左边，再处理右边——这就是 分治思想 的雏形。

六、相关知识点指引

如果你已经掌握了递归的基本原理，接下来可以继续学习：

• 分治算法：把大问题分成独立的小问题，分别解决，再合并结果（如归并排序、快速排序）。
• 回溯算法：利用递归尝试所有可能路径，走不通就回退（如迷宫求解、八皇后问题）。
• 记忆化搜索 / 动态规划：递归优化的高级形式，把子问题结果存起来，避免重复计算。
• 递归 vs 迭代：每种方法都有自己的适用场景，学会权衡。
• 栈与函数调用：深入理解计算机如何管理函数调用栈，有助于写出更可靠的递归代码。

递归是一把钥匙，打开了许多复杂问题的大门。多写几段小代码练习（比如计算阶乘、倒序打印数字、求解汉诺塔），很快你就能熟练运用它了。加油！