本课时有配套视频讲解，购买后即可观看（永久有效）
递归
一、课上练习
编程练习
递归函数展开
为了理解递归的执行过程，下面通过"讲故事"的例子对比非函数调用方式（手动展开）和函数调用方式（递归），展示递归在不同调用深度下的行为。
输出1次
非函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // tellStory(1)
6 int n = 1;
7 printf("time %d: ", n);
8 if (n == 0) {
9 printf("end\n");
10 } else {
11 printf("tell you a story:\n");
12 // tellStory(0)
13 int n = 0;
14 printf("time %d: ", n);
15 printf("end\n");
16 }
17 printf("end of %d\n", n);
18 return 0;
19}函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(1);
17 return 0;
18}输出2次
非函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // tellStory(2)
6 int n = 2;
7 printf("time %d: ", n);
8 if (n == 0) {
9 printf("end\n");
10 } else {
11 printf("tell you a story:\n");
12 // tellStory(1)
13 int n = 1;
14 printf("time %d: ", n);
15 if (n == 0) {
16 printf("end\n");
17 } else {
18 printf("tell you a story:\n");
19 // tellStory(0)
20 int n = 0;
21 printf("time %d: ", n);
22 printf("end\n");
23 }
24 printf("end of %d\n", n);
25 }
26 printf("end of %d\n", n);
27 return 0;
28}函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(2);
17 return 0;
18}输出3次
非函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n = 3;
6 printf("time %d: ", n);
7 if (n == 0) {
8 printf("end\n");
9 } else {
10 printf("tell you a story:\n");
11 // tellStory(2)
12 int n = 2;
13 printf("time %d: ", n);
14 if (n == 0) {
15 printf("end\n");
16 } else {
17 printf("tell you a story:\n");
18 // tellStory(1)
19 int n = 1;
20 printf("time %d: ", n);
21 if (n == 0) {
22 printf("end\n");
23 } else {
24 printf("tell you a story:\n");
25 // tellStory(0)
26 int n = 0;
27 printf("time %d: ", n);
28 printf("end\n");
29 }
30 printf("end of %d\n", n);
31 }
32 printf("end of %d\n", n);
33 }
34 printf("end of %d\n", n);
35 return 0;
36}函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(3);
17 return 0;
18}tellStory(3) 的递归执行过程
通过上面的代码展开，可以看到递归函数每次调用都会"嵌套"一层。下面用时序图直观展示 tellStory(3) 的完整执行过程——先逐层深入调用，再逐层返回：
正在渲染流程图...
递归(阶乘) - 函数调用与非函数调用对比
下面通过阶乘的例子，进一步对比递归函数和手动展开的写法。可以看到，随着阶乘数增大，手动展开的代码越来越复杂，而递归函数始终保持简洁。
求2的阶乘
求2的阶乘 非函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN;
6 int n = 2;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 1;
12 if (n == 1) {
13 factorialN = 1;
14 }
15 }
16 factorialN = n * factorialN;
17 }
18 cout << factorialN << endl;
19 return 0;
20}求2的阶乘 函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(2);
13 cout << factorialN << endl;
14 return 0;
15}求3的阶乘
求3的阶乘 非函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN = 0;
6 int n = 3;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 2;
12 if (n == 1) {
13 factorialN = 1;
14 } else {
15 {
16 int n = 1;
17 if (n == 1) {
18 factorialN = 1;
19 }
20 }
21 factorialN = n * factorialN;
22 }
23 }
24 factorialN = n * factorialN;
25 }
26 cout << factorialN << endl;
27 return 0;
28}求3的阶乘 函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(3);
13 cout << factorialN << endl;
14 return 0;
15}求4的阶乘
求4的阶乘 非函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN = 0;
6 int n = 4;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 3;
12 if (n == 1) {
13 factorialN = 1;
14 } else {
15 {
16 int n = 2;
17 if (n == 1) {
18 factorialN = 1;
19 } else {
20 {
21 int n = 1;
22 if (n == 1) {
23 factorialN = 1;
24 }
25 }
26 factorialN = n * factorialN;
27 }
28 }
29 factorialN = n * factorialN;
30 }
31 }
32 factorialN = n * factorialN;
33 }
34 cout << factorialN << endl;
35 return 0;
36}求4的阶乘 函数调用方式代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(4);
13 cout << factorialN << endl;
14 return 0;
15}factorial(4) 的递归执行过程
下面用时序图展示 factorial(4) 的完整递归过程——先逐层调用深入，再逐层返回计算结果：
正在渲染流程图...
二、知识总结
✨ 递归的核心思想
递归是一种解决问题的方式，即使用函数自己调用自己的方式进行循环求解。通常用来解决可以通过把问题规模逐渐缩小从而求解的问题。
常见的使用递归求解的场景有：
- 有明显递推关系的问题
- 需要使用分治思想的问题
- 数据结构操作（如树的遍历等）
递归过程中使用的函数被称作递归函数。递归函数需要包含两个部分：
- 基本情况（Base Case）：结束递归调用的条件，防止无限递归
- 递归情况（Recursive Case）：函数自己调用自己的部分，每次调用都使问题规模缩小
递归函数的执行流程
下面的流程图展示了递归函数的通用执行逻辑——每次调用时先判断是否到达基本情况，如果是则直接返回结果；否则缩小问题规模，递归调用自身，最后组合结果返回：
正在渲染流程图...
✨ 递归与调用栈
什么是调用栈？
当一个函数调用另一个函数（或调用自身）时，计算机会把当前函数的状态（局部变量、执行位置等）压入调用栈，等被调用的函数返回后，再从栈中弹出恢复执行。递归的每一层调用都会在栈中新增一层，就像叠盘子一样越叠越高。
以课上讲解的 factorial(4) 为例，调用栈的变化过程如下：
递进阶段（调用栈展开）
| 步骤 | 调用 | n 的值 | 是否到达基本情况 | 动作 |
|---|---|---|---|---|
| 1 | factorial(4) | 4 | 否 | 需要计算 4 * factorial(3)，等待 factorial(3) 的结果 |
| 2 | factorial(3) | 3 | 否 | 需要计算 3 * factorial(2)，等待 factorial(2) 的结果 |
| 3 | factorial(2) | 2 | 否 | 需要计算 2 * factorial(1)，等待 factorial(1) 的结果 |
| 4 | factorial(1) | 1 | 是 | 到达基本情况，直接返回 1 |
回归阶段（逐层返回）
| 步骤 | 返回层 | 计算过程 | 返回值 |
|---|---|---|---|
| 5 | factorial(1) | 基本情况 | 1 |
| 6 | factorial(2) | 2 factorial(1) = 2 1 | 2 |
| 7 | factorial(3) | 3 factorial(2) = 3 2 | 6 |
| 8 | factorial(4) | 4 factorial(3) = 4 6 | 24 |
最终结果：factorial(4) = 24
调用栈的深度变化
下面用更直观的方式展示递归调用时栈的深度变化——每一层缩进代表栈中新增的一层函数调用，越深代表栈越高：
1factorial(4) 被调用 ← 栈深度 1
2│
3├── factorial(3) 被调用 ← 栈深度 2
4│ │
5│ ├── factorial(2) 被调用 ← 栈深度 3
6│ │ │
7│ │ ├── factorial(1) 被调用 ← 栈深度 4（最深）
8│ │ │ └── 返回 1
9│ │ │
10│ │ └── 返回 2×1 = 2
11│ │
12│ └── 返回 3×2 = 6
13│
14└── 返回 4×6 = 24栈深度 = 递归层数。如果递归层数太深（例如 factorial(100000)），调用栈会超出系统限制，导致栈溢出（Stack Overflow）。
递归就像"俄罗斯套娃"：一层套一层地深入，直到最内层（基本情况），然后从内到外逐层打开（返回结果）。
✨ 线性递归 vs 分支递归
课上的 tellStory 和阶乘都是线性递归——每次只调用自身一次，形成一条直线调用链。但有些问题每次需要调用自身多次，形成分支递归（树形递归）。
线性递归：阶乘
每次只有一个递归调用，调用链是一条直线：
factorial(4) → factorial(3) → factorial(2) → factorial(1)时间复杂度 O(n)，调用栈深度 O(n)。
分支递归：斐波那契数列
斐波那契数列中每一项等于前两项之和：f[n] = f[n - 1] + f[n - 2]
斐波那契数列递归代码示例
1int fibonacci(int n) {
2 if (n == 1 || n == 2) {
3 return 1;
4 }
5 return fibonacci(n - 1) + fibonacci(n - 2);
6}每次有两个递归调用，形成一棵递归树——每个节点分裂为两个子问题：
正在渲染流程图...
相同颜色的节点表示重复计算：fib(3) 被计算了 2 次（黄色），fib(2) 被计算了 3 次（蓝色）。随着 n 增大，树的节点数成倍增长，时间复杂度为 O(2^n)。
下面的时序图展示了 fibonacci(5) 的完整调用和返回顺序：
正在渲染流程图...
对比总结
| 线性递归（阶乘） | 分支递归（斐波那契） | |
|---|---|---|
| 每次递归调用次数 | 1 次 | 2 次 |
| 调用结构 | 直线链 | 树形 |
| 时间复杂度 | O(n) | O(2^n) |
| 是否有重复计算 | 无 | 大量重复 |
✨ 递归示例
等差数列
等差数列中每一项与前一项的差为常数 d。
递推公式：a[n] = a[n - 1] + d
等差数列递归代码示例
1int a(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return a(n - 1) + d;
6}等比数列
等比数列中每一项与前一项的比为常数 q。
递推公式：a[n] = a[n - 1] * q
等比数列递归代码示例
1int a(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return a(n - 1) * q;
6}递推求和
求 1 到 n 的累加和：sum(n) = n + (n - 1) + ... + 2 + 1
递推公式：s[n] = s[n - 1] + n
递推求和代码示例
1int sum(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return sum(n - 1) + n;
6}✨ 递归的解题步骤
例题：用递归计算 1+2+3+...+n 的和
解题步骤：
- 找到递推关系：
sum(n) = sum(n-1) + n，即"前 n 个数的和"等于"前 n-1 个数的和"加上 n - 确定基本情况：当 n=1 时，
sum(1) = 1，不需要再递归 - 编写递归函数：
- 基本情况：
if (n == 1) return 1; - 递归情况：
return sum(n - 1) + n;
- 基本情况：
- 验证正确性：手动推演 sum(3)
- sum(3) = sum(2) + 3 = (sum(1) + 2) + 3 = (1 + 2) + 3 = 6
编写递归函数的通用模板：
第一步：明确函数的功能是什么（输入什么，输出什么）
第二步：找到递推关系（大问题如何拆成小问题）
第三步：确定基本情况（最小的问题，直接给出答案）✨ 递归的常见错误
- 忘记写基本情况：没有
if (n == 1) return 1;这样的终止条件，导致函数无限调用自身，最终栈溢出（Stack Overflow）程序崩溃 - 基本情况不正确：例如阶乘函数中写成
if (n == 0) return 0;，由于 0! = 1 而不是 0，会导致所有结果都变成 0 - 递归方向错误：问题规模没有缩小，例如写成
factorial(n + 1)而不是factorial(n - 1)，同样会导致无限递归 - 重复计算：朴素的斐波那契递归中，
fibonacci(5)会重复计算fibonacci(3)两次、fibonacci(2)三次，效率很低。当 n 较大时（如 n=40），程序会非常慢 - 混淆递推和递归：递推用循环从前往后算，递归用函数从后往前拆。两者思路相反但结果相同，注意区分使用场景