递归（recursion）是函数调用自己的过程。递归可以把复杂问题拆成更小的同类问题，但它也更容易造成重复计算和调用栈增长。
递归的两个条件
一个递归函数（recursive function）通常需要两部分：
- 基本情况（base case）：不再继续递归，直接返回结果。
- 递归情况（recursive case）：把问题缩小，然后调用自己。
如果没有基本情况，函数会一直调用自己，最终导致栈溢出（stack overflow）。
#include <cstdio>
void tell_story(void) {
std::printf("从前有座山，山里有座庙\n");
std::printf("庙里有个老和尚\n");
std::printf("老和尚在对小和尚讲故事：\n");
tell_story();
}这个函数没有停止条件，因此不能正常结束。
知识测验
阶乘
阶乘（factorial）是递归入门的经典例子。
#include <cstdio>
long factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
std::printf("5! = %ld\n", factorial(5));
return 0;
}运行结果：
5! = 120factorial(5) 不会马上得到结果。它会先调用 factorial(4)，再调用 factorial(3)，直到遇到 factorial(1)。然后结果才会一层层返回。
阶乘：先压栈，再逐层返回
解锁完整互动实验、进阶解析与精选参考答案。
知识测验
Ackermann 函数
Ackermann 函数是一个经典递归例子。它不像阶乘那样只把 n 减 1，而是根据 m 和 n 的组合进入不同递归分支。
#include <cstdio>
long ackermann(long m, long n) {
if (m == 0) {
return n + 1;
}
if (n == 0) {
return ackermann(m - 1, 1);
}
return ackermann(m - 1, ackermann(m, n - 1));
}
int main() {
std::printf("%ld\n", ackermann(2, 2));
return 0;
}运行结果：
7这个函数非常适合观察“递归里面再嵌套递归”的结构，但它增长极快。初学时只用很小的输入，例如 ackermann(2, 2) 或 ackermann(3, 1)。
下面列出 m = 0…3、n = 0…4 的结果。前三行增长还比较平缓，但 m = 3 时，每向右移动一列，结果几乎都会翻倍后再增加：
| 1 | 2 | 3 | 4 | 5 | |
| 2 | 3 | 4 | 5 | 6 | |
| 3 | 5 | 7 | 9 | 11 | |
| 5 | 13 | 29 | 61 | 125 |
没有继续列出 m = 4，因为它会从 A(4,0) = 13 很快增长到 A(4,1) = 65533，下一列已经不适合直接计算或展示。
递归的代价
递归代码常常很简洁，但每一次递归都会产生一次函数调用。如果问题规模很大，递归可能会非常慢，甚至导致栈溢出。
以斐波那契数列（Fibonacci sequence）为例：
#include <cstdio>
long fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
}
return fibonacci(n - 2) + fibonacci(n - 1);
}
int main() {
std::printf("%ld\n", fibonacci(7));
return 0;
}运行结果：
13这个递归版本会重复计算很多次。例如 fibonacci(5) 和 fibonacci(4) 内部都会继续计算 fibonacci(3)。对于较大的 n，这种重复会变得非常明显。
斐波那契：展开递归调用树
解锁完整互动实验、进阶解析与精选参考答案。
汉诺塔
有些问题天生适合递归。汉诺塔（Tower of Hanoi）的思路是：
- 把上面的
n - 1个盘子从源柱移动到辅助柱。 - 把最大盘从源柱移动到目标柱。
- 把
n - 1个盘子从辅助柱移动到目标柱。
#include <cstdio>
int move = 0;
void hanoi(int n, char src, char mid, char dst) {
if (n == 1) {
std::printf("%c -> %c\n", src, dst);
move++;
} else {
hanoi(n - 1, src, dst, mid);
std::printf("%c -> %c\n", src, dst);
move++;
hanoi(n - 1, mid, src, dst);
}
}
int main() {
hanoi(3, 'A', 'B', 'C');
std::printf("移动次数：%d\n", move);
return 0;
}运行结果：
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
移动次数：7每一步看起来只是移动一个盘子，但背后的递归任务是“先移动上面的 n - 1 个盘子，再移动最大的盘子”。下面的组件可以逐步观察盘子如何在三根柱子之间移动。
汉诺塔：亲手完成递归任务
解锁完整互动实验、进阶解析与精选参考答案。
递归不是为了“看起来高级”，而是为了让某些本来就具有自相似结构的问题更容易表达。
用递归计算 2 的 n 次方
编写 power_2(n)，在 n == 0 时停止。
- n == 0 时返回 1。
- 返回 2 * power_2(n - 1)。
- 读取 n 并打印结果。
用递归求最大公约数
实现欧几里得递归算法 gcd(a, b)。
- b == 0 时返回 a。
- 否则调用 gcd(b, a % b)。
- 读取两个整数。