C++: 递归
最后更新：2026-08-26
递归就是函数调用自己。
听起来很奇怪——函数怎么能调用自己？会不会无限循环？
只要写好"退出条件"，递归就能正常工作，而且能解决很多用循环很难写的题。
1. 什么是递归？
(1) 1.1 生活中的递归
| 生活场景 | 递归特征 |
|---|---|
| 两面相对的镜子，互相照出对方的影像 | 自己调用自己 |
| 俄罗斯套娃（打开一个，里面还有一个） | 问题分解成一个更小的同类问题 |
递归的核心思想： 把大问题分解成更小的同类问题，直到问题小到可以直接解决。
(2) 1.2 递归的两个条件
任何递归函数都必须有：
- 基线条件（Base Case）： 递归退出的条件（最简单的情况）
- 递归条件（Recursive Case）： 把问题分解成更小的同类问题
2. 递归示例：阶乘
(1) 2.1 阶乘的定义
TEXT
📖 仅展示
n! = n × (n-1) × (n-2) × ... × 1
递归定义：
TEXT
📖 仅展示
n! = n × (n-1)! （递归条件）
0! = 1 （基线条件）
▶ 示例 1：用递归计算阶乘（难度⭐⭐）
CPP
#include <iostream>
// 递归函数：计算 n 的阶乘
long long factorial(int n) {
// 基线条件
if (n == 0) {
return 1;
}
// 递归条件
return n * factorial(n - 1);
}
int main() {
int n;
std::cout << "请输入一个非负整数：";
std::cin >> n;
std::cout << n << "! = " << factorial(n) << std::endl;
return 0;
}
输出：
TEXT
📖 仅展示
请输入一个非负整数：
! =
运行效果：
TEXT
📖 仅展示
请输入一个非负整数：5
5! = 120
(2) 2.2 递归调用过程（n=5）
TEXT
📖 仅展示
factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1 × factorial(0)
= 5 × 4 × 3 × 2 × 1 × 1 ← 遇到基线条件，开始返回
= 5 × 4 × 3 × 2 × 1
= 5 × 4 × 3 × 2
= 5 × 4 × 6
= 5 × 24
= 120
💡 重点： 递归调用时，函数会暂停在 return n * factorial(n-1); 这一行，等里面的 factorial(n-1) 返回结果后，再计算 n * 结果。
3. 递归示例：斐波那契数列
(1) 3.1 斐波那契数列的定义
TEXT
📖 仅展示
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n ≥ 2）
数列：0, 1, 1, 2, 3, 5, 8, 13, 21, ...
▶ 示例 2：用递归计算斐波那契数（难度⭐⭐）
CPP
#include <iostream>
int fibonacci(int n) {
// 基线条件
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// 递归条件
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n;
std::cout << "请输入一个非负整数：";
std::cin >> n;
std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
return 0;
}
输出：
TEXT
📖 仅展示
请输入一个非负整数：
F() =
运行效果：
TEXT
📖 仅展示
请输入一个非负整数：10
F(10) = 55
💡 提示： 这个递归写法效率很低（会重复计算很多次），后面会学如何用循环或记忆化优化。
4. 递归 vs 循环
(1) 4.1 对比
| 对比 | 递归 | 循环 |
|---|---|---|
| 代码简洁度 | ⭐⭐⭐⭐⭐（某些问题更直观） | ⭐⭐⭐ |
| 效率 | ⭐⭐（函数调用有开销） | ⭐⭐⭐⭐⭐ |
| 内存占用 | 大（每次递归调用都要占栈空间） | 小 |
| 适用场景 | 问题天然递归（如树、图） | 大多数场景 |
(2) 4.2 用循环改写阶乘
CPP
#include <iostream>
long long factorial(int n) {
long long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
int main() {
int n;
std::cout << "请输入一个非负整数：";
std::cin >> n;
std::cout << n << "! = " << factorial(n) << std::endl;
return 0;
}
💡 建议： 如果问题可以用循环简单解决，优先用循环。递归适合那些"问题天然就是递归的"场景（如树的遍历、快速排序）。
5. 递归的陷阱：栈溢出
(1) 5.1 什么是栈溢出？
每次函数调用都会在调用栈上占一块空间。如果递归太深（比如几万层），调用栈就会耗尽，导致栈溢出（Stack Overflow）。
CPP
#include <iostream>
void infiniteRecursion() {
infiniteRecursion(); // ❌ 没有基线条件，无限递归
}
int main() {
infiniteRecursion();
return 0;
}
运行结果：
CPP
Segmentation fault (core dumped) // Linux
或
CPP
Process finished with exit code -1073741571 // Windows：栈溢出
(2) 5.2 如何避免栈溢出？
- 确保有基线条件，而且基线条件一定能到达
- 控制递归深度（比如用循环改写）
- 用尾递归优化（后面会学，但不是所有编译器都支持）
6. 实战：汉诺塔
▶ 示例 3：汉诺塔递归解法（难度⭐⭐⭐）
问题： 有 3 根柱子（A、B、C）和 n 个盘子。最初所有盘子都在 A 柱上（小的在上，大的在下）。要把所有盘子移到 C 柱，每次只能移一个盘子，而且任何时候都不能把大的放在小的上面。输出移动步骤。
递归思路：
- 把 n-1 个盘子从 A 移到 B（借助 C）
- 把第 n 个盘子从 A 移到 C
- 把 n-1 个盘子从 B 移到 C（借助 A）
CPP
#include <iostream>
void hanoi(int n, char from, char to, char aux) {
if (n == 1) { // 基线条件：只有一个盘子
std::cout << "把盘子 1 从 " << from << " 移到 " << to << std::endl;
return;
}
// 递归条件
hanoi(n - 1, from, aux, to); // 把 n-1 个盘子从 from 移到 aux
std::cout << "把盘子 " << n << " 从 " << from << " 移到 " << to << std::endl;
hanoi(n - 1, aux, to, from); // 把 n-1 个盘子从 aux 移到 to
}
int main() {
int n;
std::cout << "请输入盘子数量：";
std::cin >> n;
std::cout << "========== 汉诺塔移动步骤 ==========\n";
hanoi(n, 'A', 'C', 'B');
return 0;
}
输出：
TEXT
📖 仅展示
把盘子 1 从 移到
把盘子 从 移到
请输入盘子数量：
========== 汉诺塔移动步骤 ==========
运行效果（n=3）：
TEXT
📖 仅展示
========== 汉诺塔移动步骤 ==========
把盘子 1 从 A 移到 C
把盘子 2 从 A 移到 B
把盘子 1 从 C 移到 B
把盘子 3 从 A 移到 C
把盘子 1 从 B 移到 A
把盘子 2 从 B 移到 C
把盘子 1 从 A 移到 C
💡 提示： 汉诺塔的递归解法非常优雅，但如果你试着用循环写，会发现很难。这就是递归的威力。
7. 递归的优化：记忆化
(1) 7.1 问题：朴素递归效率低
前面的斐波那契递归函数会重复计算很多次：
TEXT
📖 仅展示
fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ...
fibonacci(2) 被计算了 5 次！当 n 很大时，效率极低。
(2) 7.2 解决方法：记忆化
把已经计算过的结果存起来，下次直接查表。
CPP
#include <iostream>
#include <vector>
std::vector<long long> memo; // 记忆化数组
long long fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo[n] != -1) { // 如果已经计算过，直接返回
return memo[n];
}
memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // 计算并存储
return memo[n];
}
int main() {
int n;
std::cout << "请输入一个非负整数：";
std::cin >> n;
memo.resize(n + 1, -1); // 初始化记忆化数组
std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
return 0;
}
💡 提示： C++11 引入了 std::unordered_map，可以更方便地实现记忆化。
❓ 常见问题
Q 递归和循环能互相转换吗？
A 能！任何递归都能改写成循环（用栈模拟调用栈），任何循环也能改写成递归。
Q 为什么递归效率低？
A 因为每次函数调用都有开销： > 1. 参数要压栈 > 2. 返回地址要压栈 > 3. 局部变量要分配空间
Q 所有问题都能用递归解决吗？
A 理论上是的（因为递归和循环等价），但有些问题用递归反而更复杂。
📖 小节
- 递归是函数调用自己
- 递归必须有两个条件：基线条件（退出）和递归条件（继续）
- 递归的优点是代码简洁，缺点是效率低、可能栈溢出
- 能用循环简单解决的问题，优先用循环
- 递归适合那些"问题天然就是递归的"场景
📝 作业
- 基础题 (Difficulty ⭐)：
用递归写一个函数
int sumDigits(int n)，计算一个整数的各位数字之和。
TEXT
📖 仅展示
输入：123
输出：1 + 2 + 3 = 6
（提示：递归条件 sumDigits(n) = n % 10 + sumDigits(n / 10)，基线条件 n == 0）
- 进阶题 (Difficulty ⭐⭐)：
用递归写一个函数
int power(int base, int exp)，计算 base 的 exp 次方。
TEXT
📖 仅展示
输入：power(2, 5)
输出：32
（提示：递归条件 power(b, e) = b * power(b, e-1)，基线条件 e == 0 时返回 1）
- 挑战题 (Difficulty ⭐⭐⭐)： 用递归解决"爬楼梯"问题：
- 假设你要爬 n 级楼梯，每次可以爬 1 级或 2 级
- 问有多少种不同的爬法？
- （提示：这是斐波那契数列的另一个版本——
f(n) = f(n-1) + f(n-2)） - 用记忆化优化你的递归函数
- 递归函数：自己调用自己，分拆问题再合并
- 递归三要素：终止条件、递归调用、合并结果
- 斐波那契递归是经典入门例子
- 递归 vs 循环：递归代码简洁，循环性能更好
- 尾递归可被编译器优化为循环
8. 🚀 下一步
学会了递归，接下来我们学习 函数重载和默认参数（第13课）—— 让函数更灵活、更易用的技巧！
