5.3 递归
递归（recursion）是函数调用自己的过程。递归可以把复杂问题拆成更小的同类问题，但它也更容易造成重复计算和调用栈增长。
递归的两个条件
一个递归函数（recursive function）通常需要两部分：
- 基本情况（base case）：不再继续递归，直接返回结果。
- 递归情况（recursive case）：把问题缩小，然后调用自己。
如果没有基本情况，函数会一直调用自己，最终导致栈溢出（stack overflow）。
#include <stdio.h>
void tell_story(void) {
printf("从前有座山，山里有座庙\n");
printf("庙里有个老和尚\n");
printf("老和尚在对小和尚讲故事：\n");
tell_story();
}这个函数没有停止条件，因此不能正常结束。
阶乘
阶乘（factorial）是递归入门的经典例子。
#include <stdio.h>
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
int main(void) {
printf("5! = %d\n", factorial(5));
return 0;
}运行结果：
5! = 120factorial(5) 不会马上得到结果。它会先调用 factorial(4)，再调用 factorial(3)，直到遇到 factorial(1)。然后结果才会一层层返回。
Ackermann 函数
Ackermann 函数是一个经典递归例子。它不像阶乘那样只把 n 减 1，而是根据 m 和 n 的组合进入不同递归分支。
它的递归会同时改变 m 和 n，并且增长非常快，所以示例通常只计算很小的参数。
#include <stdio.h>
int ackermann(int m, int 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(void) {
printf("%d\n", ackermann(2, 2));
return 0;
}运行结果：
7这个函数非常适合观察“递归里面再嵌套递归”的结构，但它增长极快。初学时只用很小的输入，例如 ackermann(2, 2) 或 ackermann(3, 1)。
递归的代价
递归代码常常很简洁，但每一次递归都会产生一次函数调用。如果问题规模很大，递归可能会非常慢，甚至导致栈溢出。
以斐波那契数列（Fibonacci sequence）为例：
#include <stdio.h>
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
}
return fibonacci(n - 2) + fibonacci(n - 1);
}
int main(void) {
printf("%d\n", fibonacci(7));
return 0;
}运行结果：
13这个递归版本会重复计算很多次。例如 fibonacci(5) 和 fibonacci(4) 内部都会继续计算 fibonacci(3)。对于较大的 n，这种重复会变得非常明显。
汉诺塔
有些问题天生适合递归。汉诺塔（Tower of Hanoi）的思路是：
1. 把上面的 n - 1 个盘子从源柱移动到辅助柱。
2. 把最大盘从源柱移动到目标柱。
3. 把 n - 1 个盘子从辅助柱移动到目标柱。
#include <stdio.h>
int move_count = 0;
void hanoi(int n, char src, char mid, char dst) {
if (n == 1) {
printf("%c -> %c\n", src, dst);
move_count++;
} else {
hanoi(n - 1, src, dst, mid);
printf("%c -> %c\n", src, dst);
move_count++;
hanoi(n - 1, mid, src, dst);
}
}
int main(void) {
hanoi(3, 'A', 'B', 'C');
printf("移动次数：%d\n", move_count);
return 0;
}运行结果：
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
移动次数：7每一步看起来只是移动一个盘子，但背后的递归任务是“先移动上面的 n - 1 个盘子，再移动最大的盘子”。下面的组件可以逐步观察盘子如何在三根柱子之间移动。
递归不是为了“看起来高级”，而是为了让某些本来就具有自相似结构的问题更容易表达。