第 26 章自己调用自己——递归入门

🏗️ 前情回顾：函数写顺手了——参数能传、变量有领地、作用域清清楚楚。但你有没有想过：一个函数能不能调用它自己？听起来像"左脚踩右脚飞上天"，但在编程世界里，这不仅是可能的，还是解决一大类问题的最优雅武器。这就是递归。

🎯 本章目标

学完这一章，你能：

理解递归的核心思想——把大问题拆成同类型的小问题
掌握递归三要素：边界条件、递推关系、递归调用
用递归实现阶乘和斐波那契数列
初步理解递归调用栈
知道递归和递推（循环）的区别与各自优劣
认识到递归的风险——栈溢出

📖 故事引入

你见过俄罗斯套娃吗？一个大娃娃，打开里面是一个小一点的娃娃，再打开又是一个更小的娃娃……一直开到最小的那个，它打不开了。

你站在两面镜子中间往镜子里看——镜子里有镜子，镜子里的镜子里还有镜子……一层套一层，越来越小，直到看不见。

递归就像套娃和镜子：一个大问题里面藏着一个结构相同但规模更小的问题。你不断拆下去，拆到最小的问题可以直接解决，然后一层层往回拼。

比如，如何计算 5!（5 的阶乘，即 5×4×3×2×1）？

你可能会想：我要是知道 4! 就好了，5! = 5 × 4!。

那 4! 呢？4! = 4 × 3!。

3! = 3 × 2!，2! = 2 × 1!，1! = 1。

你看：计算 5! 的问题，被一步步拆分成了"计算更小数字的阶乘"。到了 1!，答案显而易见（就是 1），不用再拆了。然后从 1! 开始往回算：2! = 2，3! = 6，4! = 24，5! = 120。

这就是递归——函数自己调用自己，每次把问题规模缩小一点，直到碰到一个可以直接解决的"最小问题"。

🧱 知识讲解

26.1 递归三要素

任何一个递归函数都必须包含三样东西，缺一不可：

要素	说明	比如阶乘
边界条件	什么情况下停止递归，直接返回	n == 1 时返回 1
递推关系	大问题怎么用小问题的答案算出来	n! = n × (n-1)!
递归调用	函数调用自己，问题规模缩小	调用 factorial(n-1)

❌ 缺少边界条件的后果——死循环崩溃：
cpp
int f(int n) { return n * f(n-1); }  // ❌ 没有if判断，一路冲向负无穷
1

❌ 参数不缩小也完蛋：

cpp

int f(int n) { if (n <= 1) return 1; return n + f(n); }  // ❌ 还是n，永远到不了边界

✅ 正确写法（三要素齐全）：

缺少边界条件 → 无限递归 → 程序崩溃。缺少递推关系 → 递归没有意义。

26.2 阶乘：递归的"Hello World"

cpp

int factorial(int n) {
    if (n == 1) {                // 边界条件：1! = 1
        return 1;
    }
    return n * factorial(n - 1); // 递推 + 递归调用
}

int main() {
    cout << factorial(5) << endl; // 120
    return 0;
}

跟踪一下 factorial(3) 的执行过程：

factorial(3)
  → 3 * factorial(2)
       → 2 * factorial(1)
            → 1                                ← 边界条件，开始返回
       → 2 * 1 = 2                             ← 返回 2
  → 3 * 2 = 6                                  ← 返回 6

就像剥洋葱：一层层剥进去（调用），剥到最中心，再一层层拼回来（返回）。

26.3 斐波那契数列

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, ...

规律：从第 3 项开始，每一项 = 前两项之和。即 F(n) = F(n-1) + F(n-2)。

边界条件：F(1) = 1, F(2) = 1。

cpp

int fib(int n) {
    if (n == 1 || n == 2) {      // 边界条件
        return 1;
    }
    return fib(n - 1) + fib(n - 2); // 递推关系 + 两个递归调用
}

int main() {
    cout << fib(7) << endl;      // 13
    return 0;
}

注意：fib(n) 的递归调用会展开成一棵"树"——fib(5) 调用 fib(4) 和 fib(3)，而 fib(4) 又调用 fib(3) 和 fib(2)……同一个值（比如 fib(3)）会被重复计算很多次。所以纯递归的斐波那契在 n 较大时非常慢。后面你会学到用"记忆化"或递推来优化它。

26.4 递归调用栈

每次函数调用，计算机会在内存的一个特殊区域——调用栈（Call Stack）上开辟一小块空间，用来存参数、局部变量和"返回地址"（从哪调用的，算完回哪去）。

递归调用时，这些空间一块块叠上去：

调用 factorial(3)：   栈顶 → [n=3, 返回地址]
调用 factorial(2)：   栈顶 → [n=2, 返回地址]  ← 叠在上一层之上
调用 factorial(1)：   栈顶 → [n=1, 返回地址]  ← 再叠一层
到达边界，开始返回 ←
返回 factorial(1)=1： 栈顶弹出 [n=1]
返回 factorial(2)=2： 栈顶弹出 [n=2]
返回 factorial(3)=6： 栈顶弹出 [n=3]

每一层递归调用都会在栈上占用空间。如果递归层次太深（比如 factorial(100000)），栈空间会被耗尽，程序崩溃——这就是著名的栈溢出（Stack Overflow）。

⚠️ 递归层数通常不要超过几千到几万层（取决于系统和栈大小）。信息学竞赛中，如果递归深度可能很大，要考虑改用递推（循环）或增大栈空间。

26.5 递归 vs 递推

	递归	递推（循环）
写法	简洁优雅，贴近数学定义	用循环，稍显啰嗦
思路	自顶向下（从大问题拆到小问题）	自底向上（从小问题算到大问题）
效率	可能重复计算，占用栈空间	通常更快，不占栈空间
适用场景	天生递归的问题（树、分治）	线性递推（阶乘、斐波那契）

阶乘的递推写法：

cpp

int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

斐波那契的递推写法：

cpp

int fib(int n) {
    if (n == 1 || n == 2) return 1;
    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

🧠 初学阶段，先用递归理解问题的"分拆"本质；顺手之后，再学递推优化。两者是同一个思维的两种写法，不是敌人。

26.6 递归的更多例子

倒序输出数字的每一位：

cpp

void printDigits(int n) {
    if (n < 10) {                  // 边界：只剩一位
        cout << n << " ";
        return;
    }
    cout << n % 10 << " ";         // 先输出个位
    printDigits(n / 10);           // 再处理剩下的
}
// printDigits(1234) → "4 3 2 1 "

计算最大公约数（辗转相除法递归版）：

cpp

int gcd(int a, int b) {
    if (b == 0) return a;          // 边界条件
    return gcd(b, a % b);          // 递推关系：gcd(a,b) = gcd(b, a%b)
}

这是你见过的第一个"尾递归"——递归调用是函数的最后一步。聪明的编译器可以把它优化成循环，不消耗栈空间。

✋ 动手试试

试试 1：写递归函数 int sum(int n)，返回 1 到 n 的和。比如 sum(100) 返回 5050。然后试着输入一个非常大的 n（如 100000），观察会发生什么。

试试 2：写递归函数 void countDown(int n)，从 n 倒数到 1（每行一个数字），然后输出"发射！"。比如 countDown(5) 输出 5, 4, 3, 2, 1, 发射！

试试 3：用递归实现"汉诺塔"的输出（只需要输出步骤，不需要图形）。输入盘子数 n（建议从 3 开始，别太大），输出移动步骤。

提示：把 n 个盘子从 A 移到 C（可借助 B），步骤是：

把 n-1 个盘子从 A 移到 B（借助 C）
把第 n 个盘子从 A 移到 C
把 n-1 个盘子从 B 移到 C（借助 A）

🦶 你踩过这些坑吗

逐一核对，看你是不是也中过招：

[ ] 忘了边界条件：int f(int n) { return n * f(n-1); } ← 没有 if 终止条件，无限递归直到栈溢出崩溃 → ✅ 必须加边界：if (n <= 1) return 1;
[ ] 边界条件永远触发不了：if (n == 0) return 0; 但参数从 1 开始且递减——不一定到 0 → ✅ 确保参数变化方向最终能碰到边界条件
[ ] 递归参数没有缩小：int f(int n) { return n + f(n); } ← n 没变，永远到不了边界 → ✅ 每次递归参数必须向边界靠近：f(n-1)
[ ] 递归太深导致栈溢出：用纯递归算 fib(100) 或 factorial(100000) → ✅ 深度大或重复计算多的场景，改用递推（循环）

📝 练习

基础题

1. 选择题

（1）递归函数必须包含：
A. 循环 B. 边界条件 C. 全局变量 D. void 返回类型

（2）factorial(3) 一共进行了几次函数调用（包括初始调用）？
A. 1 B. 2 C. 3 D. 4

（3）以下哪项是栈溢出的原因？
A. 递归层数太深 B. 数组越界 C. 除以零 D. 变量未初始化

2. 填空题

（1）递归三要素是：____、____、____。

（2）阶乘的递推关系是 n! = n × ____。

（3）斐波那契数列前两项分别是 ____ 和 ____。

3. 判断题

（1）任何递归函数都可以等价地改写为递推（循环）形式。（）

（2）递归函数每调用自己一次，就会在栈上分配新的空间。（）

4. 读代码写结果

cpp

int mystery(int n) {
    if (n == 0) return 0;
    return n % 10 + mystery(n / 10);
}
int main() {
    cout << mystery(1234);
}

输出：_____

提高题

5. 编程题 — 求幂运算

写一个递归函数 int power(int a, int n)，计算 a 的 n 次方（a^n）。边界：n == 0 时返回 1。递推：a^n = a × a^(n-1)。

6. 编程题 — 数字之和

写一个递归函数 int digitSum(int n)，返回 n 的各位数字之和。比如 digitSum(1234) 返回 10。

提示：n % 10 取个位，n / 10 去掉个位。递推：digitSum(n) = n%10 + digitSum(n/10)。

7. 编程题 — 最大公约数（递归版）

用辗转相除法写一个递归函数 int gcd(int a, int b)，计算 a 和 b 的最大公约数。

递推关系：gcd(a, b) = gcd(b, a % b)，边界条件：b == 0 时返回 a。

挑战题

8. 编程题 — 汉诺塔

输入一个整数 n（盘子数），输出将所有盘子从 A 柱移到 C 柱的步骤。

示例：n = 3

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

（提示：函数签名 void hanoi(int n, char from, char to, char aux)，其中 aux 是辅助柱。）

9. 编程题 — 爬楼梯问题

假设你正在爬楼梯，需要走 n 阶才能到达楼顶。每次你可以爬 1 阶或 2 阶。你有多少种不同的方法可以爬到楼顶？

用递归函数 int climbStairs(int n) 解决。

示例：n=3 → 输出 3（方法：1+1+1、1+2、2+1）

（提示：递推关系 climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)，边界 n==1 返回 1，n==2 返回 2。这其实就是斐波那契！）

🧠 本章小结

递归 = 函数自己调用自己

三要素：
  ① 边界条件 —— 停止递归的底线（没有它 = 无限循环）
  ② 递推关系 —— 大问题怎么拆成小问题
  ③ 递归调用 —— 调用自己，问题规模必须缩小

经典例子：
  阶乘    n! = n × (n-1)!    边界 n==1
  斐波那契 F(n) = F(n-1)+F(n-2) 边界 n==1,2

递归 vs 递推：
  递归 = 自顶向下，优雅但可能慢
  递推 = 自底向上，高效但稍啰嗦

风险：递归太深 → 栈溢出（Stack Overflow）

📝 配套练习

共7题。从单分支→双分支→逆推→记忆化，递归的四种形态逐步展开。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	J0104	https://hydro.ac/d/srqc/p/J0104	递归三要素、阶乘
◆ 拓展	J0057	https://hydro.ac/d/srqc/p/J0057	斐波那契、双分支递归
◆ 拓展	J0113	https://hydro.ac/d/srqc/p/J0113	逆推递归、while对比
◆ 拓展	luogu-P1028	https://hydro.ac/p/luogu-P1028	递归+记忆化启蒙
◆ 拓展	luogu-P1044	https://hydro.ac/p/luogu-P1044	递归、栈序列、卡特兰启蒙
◆ 拓展	luogu-P5739	https://hydro.ac/p/luogu-P5739	递归阶乘、基础模板
◆ 拓展	luogu-P5740	https://hydro.ac/p/luogu-P5740	递归斐波那契

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。

配套练习

共7题。从单分支→双分支→逆推→记忆化，递归的四种形态逐步展开。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	J0104	https://hydro.ac/d/srqc/p/J0104	递归三要素、阶乘
◆ 拓展	J0057	https://hydro.ac/d/srqc/p/J0057	斐波那契、双分支递归
◆ 拓展	J0113	https://hydro.ac/d/srqc/p/J0113	逆推递归、while对比
◆ 拓展	luogu-P1028	https://hydro.ac/p/luogu-P1028	递归+记忆化启蒙
◆ 拓展	luogu-P1044	https://hydro.ac/p/luogu-P1044	递归、栈序列、卡特兰启蒙
◆ 拓展	luogu-P5739	https://hydro.ac/p/luogu-P5739	递归阶乘、基础模板
◆ 拓展	luogu-P5740	https://hydro.ac/p/luogu-P5740	递归斐波那契

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我理解递归的思想：把大问题拆成同类型小问题
[ ] 我能写出递归的三要素（边界、递推、调用）
[ ] 我能用递归实现阶乘和斐波那契
[ ] 我大致理解调用栈的"层层叠放"
[ ] 我知道递归和递推的各自优劣
[ ] 我知道栈溢出是什么以及如何避免

🚀 下章预告：递归打开了新世界——用函数调用自己解决复杂问题。但数据和变量还是散的：一个学生有名字、年龄、分数三个信息，难道要声明三个数组分别存？能不能像档案袋一样，把同一个人的信息打包在一起？第 27 章——结构体 struct，让你的数据告别零散。

第 26 章 自己调用自己——递归入门 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

26.1 递归三要素 ​

26.2 阶乘：递归的"Hello World" ​

26.3 斐波那契数列 ​

26.4 递归调用栈 ​

26.5 递归 vs 递推 ​

26.6 递归的更多例子 ​

✋ 动手试试 ​

🦶 你踩过这些坑吗 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​