第 9 章 · 递归与分治

递归 = 函数调用自己；每次调用在系统栈压一个新栈帧。

9.1 递归本质：函数栈帧

int fact(int n) {
    if (n <= 1) return 1;      // 终止条件（基线）
    return n * fact(n - 1);    // 递归缩小问题
}

fact(3) 依次压入 fact(3)→fact(2)→fact(1) 三栈帧，到基线逐层弹回（见 C 指针第 2 章）。代价是每层一栈帧，深递归会栈溢出。

9.2 汉诺塔

把 n 个盘子从 A 移到 C（B 辅助），每次只能移一个、大盘不压小盘。

void hanoi(int n, char a, char b, char c) {
    if (n == 1) { printf("%c -> %c\n", a, c); return; }
    hanoi(n - 1, a, c, b);      // 先把上面 n-1 个搬到辅助柱
    printf("%c -> %c\n", a, c);
    hanoi(n - 1, b, a, c);      // 再把 n-1 个搬过来
}

T(n) = 2T(n−1) + 1 = 2ⁿ − 1，指数级（见第 1 章）。

9.3 分治：拆、治、合

分治把大问题拆成若干独立子问题，递归求解后合并。三步：

1. 分解：分成相同形式的子问题；
2. 求解：子问题足够小直接解，否则递归；
3. 合并：子问题的解合成原问题的解。

• 归并排序（第 8 章）：拆两半 → 各自排 → 合并。合并是主体。
• 快排（第 8 章）：划分（partition）是主体，子数组自然有序无需合并。
• 二分查找（第 7 章）：每步丢弃一半，是「减治」的分治特例。

9.4 递归 vs 迭代

// 迭代版阶乘：O(1) 额外空间，无栈帧压力
int fact_it(int n) { int r = 1; for (int i = 2; i <= n; i++) r *= i; return r; }

	递归	迭代
空间	O(深度) 栈帧	O(1)
可读性	贴近问题定义	显式循环，需维护状态
风险	栈溢出	无（除非死循环）
尾递归优化	可被编译成循环	—

能用尾递归写时，编译器可能优化成循环（不涨栈）。但 C 标准不保证尾调用优化，深度敏感处仍优先迭代或显式栈（第 5 章非递归遍历）。

对比：递归赢表达力（树/图遍历天然递归），输栈帧开销与溢出；迭代赢常数与空间，输可读性。

对比：分治拆多个子问题再合并（归并、快排）；减治只留一个子问题、规模减一/减半（汉诺塔、二分）。