前置知识: C

递归与分治：把问题交给更小的自己

13 min入门

以"逐帧追踪 factorial 栈展开"为主线学 C 递归：基准情况与递归步的完整推论、汉诺塔与猴子吃桃两道经典、间接递归与前置声明、栈深实测与尾递归的真实边界、分治三步与二分查找，附防 int 溢出的中点写法与四道遮代码自检练习。

前置知识

  • 已完成 函数详解 第 5 节：知道基准情况、递归步两个必要件，见过朴素 fib 的重复计算问题；
  • 知道每次函数调用会在栈上压一层帧——帧里到底有什么，函数调用栈帧 是本文的”底层视角”补充；
  • 了解 int 与 long long 的取值范围（见 数据类型详解），本文会反复用到。

学习目标

  1. 用”调用链 + 返回链”两段话描述任意递归函数的执行过程，并能画出 factorial(4) 的栈展开图；
  2. 独立写出汉诺塔与猴子吃桃的递归解，并说出它们各自”缩小问题”的方式；
  3. 解释间接递归为什么必须先有函数原型，以及全局变量混入递归时的经典事故；
  4. 实测自己平台的栈深上限，说清尾递归在 C 里为什么不能当优化承诺；
  5. 描述分治三步（划分、求解、合并），并用递归写出带防溢出中点的二分查找。

预计 45 到 60 分钟。

1. 问题引入：同一行代码的两次人生

090 篇用两行代码引出了递归：

c
if (n <= 1) return 1;          /* 基准情况 */
return n * factorial(n - 1);   /* 递归步 */

很多人背到这里就停了，于是面对汉诺塔时完全无从下手——因为阶乘的递归是”一条线”的，而汉诺塔是”分叉”的。本文的主线任务：把递归从”背模式”变成”看得见的机械过程”，这样任何新递归题都只是同一个过程的变体。

2. 先试试看：让递归自己交代自己的行踪

在递归函数里打印调用深度与局部变量地址，递归的执行过程就从黑盒变成仪表盘：

c
/* trace_fact.c：逐帧追踪 factorial */
#include <stdio.h>

long factorial(int n, int depth) {
    printf("进入 depth=%d, n=%d, 局部地址=%p\n", depth, n, (void *)&n);
    long result;
    if (n <= 1) {
        result = 1;
    } else {
        result = (long)n * factorial(n - 1, depth + 1);
    }
    printf("退出 depth=%d, 返回 %ld\n", depth, result);
    return result;
}

int main(void) {
    printf("结果 = %ld\n", factorial(4, 0));
    return 0;
}
text
进入 depth=0, n=4, 局部地址=0x0061FEF0
进入 depth=1, n=3, 局部地址=0x0061FEA0
进入 depth=2, n=2, 局部地址=0x0061FE50
进入 depth=3, n=1, 局部地址=0x0061FE00
退出 depth=3, 返回 1
退出 depth=2, 返回 2
退出 depth=1, 返回 6
退出 depth=0, 返回 24
结果 = 24

三行结论，全部来自这次观察：

  1. 进入是”下潜”，退出是”回升”：打印顺序天然分成两段——先一路”进入”到基准情况，再一路”退出”把结果带回来。任何递归程序都是这两个阶段，缺一不可；
  2. 每层帧是独立副本：四个 depth 变量的地址依次减小（栈向下生长），说明每一层调用都有自己的局部变量，互不干扰——这就是”传值”在递归里的含义；
  3. 深度有上限：地址在 4 层里下降了约 0x50（80 字节）。照这个速度，百万层递归需要几十 MB 栈。栈到底有多大？下一节实测。

3. 栈深上限：测出你这台机器的天花板

递归深度受栈大小限制，而栈大小因平台而异：Windows 上链接器默认栈通常 1 到 2 MB（MSVC 约 1 MB，MinGW 约 2 MB），Linux 常见 8 MB。与其背数字，不如在自己的环境里测出来：

bash
# Linux / Git Bash：查看当前栈上限（单位 KB）
ulimit -s
c
/* stack_probe.c：无基准情况的"纯下潜"，用崩溃点测栈深 */
#include <stdio.h>

int depth = 0;

void dive(void) {
    char pad[1024];      /* 每层故意压 1KB，方便估算 */
    pad[0] = 1;
    depth++;
    dive();              /* 永远不返回：只为观察崩在哪 */
}

int main(void) {
    dive();
    return 0;
}

典型输出（数字随平台不同，以你的实测为准）：

text
栈上限 8192 KB，约 2 万次 dive 后段错误
每层约 1KB 帧加少量开销，与 8 MB 上限数量级吻合

这段代码故意没有基准情况，用来做实验可以，写进工程就是事故。工程结论：树高、链表长不可控时，递归深度就是不可控的——输入规模决定你是否该改写为循环（第 8 节给出方法）。

4. 经典两例：一条线与分叉的树

4.1 汉诺塔：把”分叉”写进递归步

题目：三根柱子，n 个盘子按大小摞在第一根，每次移动一个盘，大盘不能压小盘，全部挪到第三根。

直接想”第 1 步移哪个”会失败。换问法：要把 n 个盘从 A 挪到 C，谁帮我们处理上面 n-1 个盘？ 答案是”更小的自己”：

c
/* hanoi.c：n 个盘从 from 借助 mid 挪到 to */
#include <stdio.h>

long moves = 0;

void hanoi(int n, char from, char mid, char to) {
    if (n == 0) {                    /* 基准情况：没有盘可挪 */
        return;
    }
    hanoi(n - 1, from, to, mid);     /* 1. 把上面 n-1 个盘让路到中转柱 */
    printf("盘 %d: %c -> %c\n", n, from, to);
    moves++;                         /* 2. 挪最大的盘 */
    hanoi(n - 1, mid, from, to);     /* 3. 把 n-1 个盘从中转柱归位 */
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    printf("总步数 = %ld\n", moves); /* 7 = 2^3 - 1 */
    return 0;
}
text
盘 1: A -> C
盘 2: A -> B
盘 1: C -> B
盘 3: A -> C
盘 1: B -> A
盘 2: B -> C
盘 1: A -> C
总步数 = 7

与阶乘的区别在于：递归步调用自己两次（问题分叉成两半），基准情况是”无事可做”而不是”返回一个值”。总步数满足 f(n) = 2*f(n-1) + 1，展开得 2^n - 1——n=64 时约 1.8 × 10^19，全宇宙的原子搬完也搬不完，这就是递归把”直觉上简单”的问题指数放大的著名例证。

4.2 猴子吃桃：倒着递归的思维方式

题目：某猴第 1 天摘了一堆桃，从第 2 天起每天吃掉前一天剩下的一半再加一个；到第 10 天早上只剩 1 个。问第 1 天共摘了多少个？

正向想”第 1 天有多少”没有入口。倒着想：知道第 n+1 天剩多少，第 n 天是多少？ 剩下的是”吃掉一半再加一”之后的，所以前一天 = (当天 + 1) × 2：

c
long peach(int day) {
    if (day == 10) {               /* 基准情况：题目给的终点 */
        return 1;
    }
    return (peach(day + 1) + 1) * 2;
}
/* peach(1) == 1534 */

它的价值不在答案（1534），而在方法：递归的方向不必与时间的方向一致。很多”给定终点求起点”的题（约瑟夫环 survivor、递归下降解析）都是这个套路——把题目给定的锚点设为基准情况，把”倒推关系”写成递归步。

4.3 间接递归：调用环与前置声明

递归不一定是”自己调用自己”。A 调 B、B 调 A，同样构成递归：

c
int is_odd(int n);                    /* 前置声明：原型先行 */

int is_even(int n) {
    if (n == 0) return 1;
    return is_odd(n - 1);
}

int is_odd(int n) {
    if (n == 0) return 0;
    return is_even(n - 1);
}

把两个定义的顺序对调且删掉原型，编译器在解析 is_even 时还没见过 is_odd，报 implicit declaration。这条规则 090 篇讲过一半（“先定义后调用”），递归把它变成了硬需求：任何调用环上，至少需要一个原型打破顺序。更隐蔽的推论是：调用环上的基准情况可能”绕一圈”才被触达，漏写或写错其中一个基准，程序不会报错，只会算错。

5. 坑点与自检

坑 1：基准情况不可达。 factorial(n) 的递归步写 factorial(n)（忘了 -1）或基准写 n == 1 却从 n = 2 以下传入负数方向——每次调用都在”下潜”却永远到不了终点，崩在栈溢出而不是逻辑错误。写完递归先单独验证：传入最小输入，基准是否被触发。

坑 2：整型溢出伪装成逻辑错误。 32 位 int 在 13! 就溢出（12! = 479001600 尚可，13! = 6227020800 超出 INT_MAX），long long 也在 21! 越界。溢出不报错，结果”看起来像那么回事”。递归累乘累加类题目，先估算结果量级再选类型，必要时在递归步里做范围检查。

坑 3：每层复制大结构体。 递归传参按值复制：一层的 struct Student 100 字节，深度 1 万就是 1 MB 起步的复制与栈占用。递归函数传指针（只复制一个地址），这一条同时是性能优化与栈深保险。

坑 4：用全局变量当”层内状态”。 想在递归里维护”当前累计值”时伸手就建全局变量——间接递归、多线程、重入场景立刻互相污染。层内状态放参数（像 trace_fact 的 depth），跨层聚合用返回值。

坑 5：把尾递归当优化承诺。 递归调用是函数体最后一个动作、且不需要保留任何本地计算（return factorial(n-1, acc*n) 这种形态）叫尾递归。编译器可以把它优化成循环（GCC/Clang 在 -O2 下经常这么做），但 C 标准不要求——依赖”尾递归一定不爆栈”的代码在别的编译器或 -O0 下就是事故。C 里的可靠做法是把改写循环当成自己的责任，优化器给的是惊喜而非契约。

自检——能不看文档回答吗：

  1. factorial(4) 的”进入”打印与”退出”打印各是什么顺序？为什么必然是这个顺序？
  2. 汉诺塔的递归步里两次自我调用分别解决什么子问题？基准情况为什么是 n == 0？
  3. 猴子吃桃把”终点”设为基准情况，这个思路还能用在什么题上？
  4. 间接递归为什么必须前置声明？不声明会得到什么报错？
  5. 你的平台栈上限是多少？怎么测出来？每层帧的大小取决于什么？
  6. 尾递归与普通递归的形式区别是什么？为什么 C 工程不把 TCO 当依赖？

6. 分治：递归的工程形态

递归步把问题分成几半、分别求解、再合并结果——这个结构就是分治（divide and conquer），三步记住：划分、求解、合并。

  • 阶乘是”分治”的退化形：分出一半是 n-1，合并是乘一次；
  • 汉诺塔是标准形：划分（上面的盘 / 最大的盘），求解（两次递归），合并（三步顺序即合并逻辑）；
  • 二分查找是最实用的形：每次把查找区间砍半，“合并”环节退化成”返回”。
c
/* bsearch_rec.c：递归二分查找，注意防溢出的中点写法 */
#include <stdio.h>

/* 在 [lo, hi] 闭区间内找 target，返回下标；找不到返回 -1 */
int binary_search(const int *a, int lo, int hi, int target) {
    if (lo > hi) {                       /* 基准情况：区间为空 */
        return -1;
    }
    int mid = lo + (hi - lo) / 2;        /* 防 int 溢出：不写 (lo+hi)/2 */
    if (a[mid] == target) {
        return mid;
    }
    if (a[mid] < target) {
        return binary_search(a, mid + 1, hi, target);
    }
    return binary_search(a, lo, mid - 1, target);
}

int main(void) {
    int a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    printf("%d\n", binary_search(a, 0, 9, 23));  /* 5 */
    printf("%d\n", binary_search(a, 0, 9, 40));  /* -1 */
    return 0;
}

(lo + hi) / 2 的隐患：lo、hi 都接近 INT_MAX 时相加溢出为负。lo + (hi - lo) / 2 数学上等价、机器上安全——这是面试里”二分查找写对了没有”的经典检查点。二分每层区间减半，深度 O(log n)：10 亿个元素也只有约 30 层递归，栈深毫无压力——深度可控的递归才是好递归。

分治的完整版（归并排序、快速排序）与”划分后合并的代价决定复杂度”的分析，在算法模块展开；本文给你的是它在 C 里的落点：递归步 + 终止条件 + 参数上传递区间（指针 + 下标，呼应坑 3）。

7. 递归改循环：显式栈思想

任何递归都能改成循环，代价是要自己管理”还没做完的事”。一条线的递归（阶乘、猴子吃桃）用一个变量就够：

c
/* 猴子吃桃的循环版：从第 10 天倒推到第 1 天 */
long peach_loop(void) {
    long total = 1;
    for (int day = 9; day >= 1; day--) {
        total = (total + 1) * 2;
    }
    return total;
}

分叉的递归（树遍历、表达式求值）改写时用一个自己管理的栈保存”待办分支”——不是每个场景都值得改，判断标准仍是 090 篇那句：哪个写法更像问题本身。深度不可控（数据规模决定）必须改；深度 O(log n)（二分、快排平均）保留递归；深度 O(n) 但 n 有上界且小（棋盘 8 行）随意。

8. 动手实践

先只读任务与提示，自己写完、跑通，再对参考实现。

  1. 帧地址观察：改写 trace_fact.c，在进入时打印本层 &depth 的地址，n 从 1 到 3 三次运行。任务：记录相邻两层地址差，估算每层帧的大小；把 n 改大直到栈溢出，记录崩溃前的最后深度，与 ulimit -s 的栈上限互相印证。提示：地址差不是精确帧大小（还有对齐与返回地址），估数量级即可。

参考实现骨架：

c
printf("depth=%d 地址=%p 差值可用相邻两次相减观察\n", depth, (void *)&depth);
/* 运行记录：本机每层约 XX 字节，崩在约 XXXXX 层，
   与 ulimit -s 的 XXXX KB 上限数量级一致 */
  1. 汉诺塔验证器：给 hanoi 加 moves 计数，跑 n = 1 到 20，验证每行输出 n、步数、2^n - 1 三者一致。任务：再回答——n = 64 的步数用 long long 存得下吗？（2^64 - 1 恰是 unsigned long long 的上限，long long 装不下，需要 unsigned。）

参考实现：

c
for (int n = 1; n <= 20; n++) {
    moves = 0;
    hanoi(n, 'A', 'B', 'C');
    long long expect = (1LL << n) - 1;        /* 2^n - 1 */
    printf("n=%2d moves=%lld expect=%lld %s\n",
           n, moves, expect, moves == expect ? "OK" : "MISMATCH");
}
  1. 猴子吃桃双实现互验：写出递归版（第 4.2 节）与循环版（第 7 节），main 里断言两者相等，再各自加一层”打印每天的剩余数”，确认倒推过程一致。提示：循环版的循环变量从 9 倒到 1，因为第 10 天是基准不是推算对象。

参考实现：

c
#include <assert.h>

int main(void) {
    assert(peach(1) == peach_loop());
    printf("第 1 天共 %ld 个桃\n", peach(1));   /* 1534 */
    return 0;
}
  1. 修 Bug 题：下面的”二分查找”有三个 bug：两个逻辑、一个溢出隐患。先指出全部三处再修正：
c
int bs(const int *a, int lo, int hi, int t) {
    int mid = (lo + hi) / 2;
    if (a[mid] == t) return mid;
    if (a[mid] < t) return bs(a, mid, hi, t);
    return bs(a, lo, mid, t);
}

参考答案：一、缺基准情况——区间缩到空时（找不到 t）mid 越界或死递归；二、递归区间写 mid 而非 mid + 1/mid - 1，当区间只剩一个元素且不等于 t 时永远自我调用（死递归，这正是基准不可达的坑 1）；三、(lo + hi) / 2 有溢出隐患，应为 lo + (hi - lo) / 2。修正版见第 6 节 binary_search。

  1. 挑战题：朴素 fib 在 090 篇算 fib(30) 要 269 万次调用。写记忆化版本：一个 long long cache[N] 数组，fib 先查缓存、算过就存。任务：对比两版算 fib(40) 的耗时（time 命令或 clock 粗测），把”重复子问题”从一句话变成你亲手测出的数字。提示：缓存数组初始化为 -1 表示”没算过”；缓存版递归深度仍是 n，注意栈。

9. 与之前和之后的知识的关系

  • 往前：090 第 5 节给了递归的最小闭环（基准 + 递归步），本文补上执行过程的可见性、分叉形态与工程边界；函数原型（090 第 2 节）在间接递归里从”好习惯”升级为”必需品”；
  • 往后：函数调用栈帧 解释本文反复出现的”每层帧多大、栈为何向下生长”；递归是理解 指针深度解析 中链式结构（链表、树）遍历的钥匙，也是毕业项目（595 篇）里哈希表 rehash 类”自我重复”逻辑的思维底座；
  • 更远：分治在算法模块有完整的复杂度分析（主定理）；解析器、目录树遍历、JSON 嵌套结构处理，本质都是本文的递归加了不同的数据形态。

10. 自我检查

  • 能画出 factorial(4) 的栈展开两阶段图，并解释地址为什么递减；
  • 能独立写出汉诺塔并说出 2^n - 1 的来源；
  • 能说出基准情况、间接递归原型、大结构体传参、溢出四个坑的对策；
  • 实测过自己平台的栈深，能给出一个数量级；
  • 能写出防溢出中点的二分查找，并指出 (lo+hi)/2 的错法。

本章总结

递归是”函数调用自己”的机械过程，不是魔法：进入段逐层下潜、退出段逐层带回，每层帧互不干扰，深度受实测的栈上限约束。一条线的问题（阶乘、猴子吃桃）递归与循环等价，分叉的问题（汉诺塔、二分）递归更贴题，深度不可控的问题必须改循环。分治把”交给更小的自己”工程化为划分-求解-合并，防溢出中点写法是二分的标志性细节。所有坑——基准不可达、溢出、每层复制、全局状态、尾递归迷信——都能在”看得见的栈”里找到根源。

下一步