第 9 章 · 递归与分治

递归大概是这门课里「第一次见觉得玄,想通之后再也回不去」的思想。它的全部内容一句话:问题的解可以由「更小规模的同构问题」的解构造出来。本章把三样东西讲透:递归在机器上的真实成本(栈帧,计组第 10 章的知识在这里兑现)、递归复杂度的算术(递推式)、以及它最成功的应用形态「分治」。学完这章,前面快排、归并、树遍历里「理所当然」的递归,你会知道它们各自为什么那样拆、合并代价是什么、以及什么情况下必须放弃递归。

9.1 递归在机器上长什么样

每个函数调用,系统栈压一个栈帧(局部变量、返回地址),返回时弹出。递归 = 自己给自己压栈,fact(3) 的执行轨迹:

main → fact(3) → fact(2) → fact(1)      压栈三帧(下到基线)
main ← 6      ← 2*3    ← 1*2           逐层弹回(算上去)

这解释了递归的两个天性:深度受栈空间限制(Linux 默认 8MB,深度百万的递归必爆栈,操作系统课 2 章的练习量过这个数),以及每层调用有真实开销(压栈、跳转、弹栈)。所以「递归 vs 迭代」从来不是美学之争,是成本之争:树的遍历、快排这类「深度 O(log n)」的递归安全且优雅;链表遍历(O(n) 深度)就纯属浪费,一层循环更实在。

9.2 递推式:给递归算笔账

递归的运行时间天然写成递推式,直接展开就能解。汉诺塔(移动 n 个盘 = 先移 n-1 个到辅助柱、移最大的、再移 n-1 个回来):

$T(n) = 2T(n-1) + 1, \quad T(1) = 1$

展开:T(n) = 2(2T(n-2)+1)+1 = 4T(n-2)+3 = … = 2ⁿ - 1。64 个盘子要移 2⁶⁴ - 1 ≈ 1.8×10¹⁹ 次,僧侣们移完世界就终结的传说,数学上是认真的(每秒一次也要五千多亿年)。

更常用的是「分成 b 份、每份 a 个、合并 O(nᵈ)」的主定理(第 8 章的算法在这章结算):

递推式	解	对应算法
T(n) = T(n/2) + O(1)	O(log n)	二分查找
T(n) = 2T(n/2) + O(n)	O(n log n)	归并排序
T(n) = 2T(n/2)(无合并)	O(n)	树遍历
T(n) = T(n-1) + O(n)	O(n²)	最坏快排

读表读出规律:合并代价决定命运。归并合并 O(n) 是主要工作,n log n;树遍历合并 O(1)(只是访问自己),总代价被 n 个节点封顶 O(n)。以后写递归,先问自己「每次递归后我做了多少额外工作」,复杂度当场现形。

9.3 分治:递归的工业形态

分治把递归模板化成三拍:分解、求解、合并。它的威力在于子问题独立(互不依赖,可以各自为政,甚至并行)。前面章节已经交过两份完美作业,对比一下能看清分治设计的两个流派:

• 归并派:合并是主体。拆成两半(几乎免费),递归排好,重活全在合并(有序序列归并)。合并代价 O(n),总计 O(n log n)。
• 快排派:分解是主体。partition 一趟 O(n) 把数组劈成「小于轴 / 轴 / 大于轴」,劈完天然有序,合并零成本。平均也是 O(n log n),但劈得歪就 O(n²)(第 8 章讲过的软肋,根源在分解质量)。

一个「分治思维」的实例,没有代码但值得走一遍:大整数乘法。两个 n 位数相乘,朴素 O(n²);分治拆成各半,朴素做法 4 次子乘法,复杂度没变;Karatsuba 的观察是把 4 次减到 3 次(用一次加法换一次乘法),递推式 T(n) = 3T(n/2) + O(n),解出 O(n^1.585)。这个例子给分治思想的精髓立了碑:分治的收益不在「拆」,在拆完之后能否减少子问题的数量或合并的代价。

9.4 什么时候必须放弃递归

三条例外清单,每条都有真实事故背书:

• 深度线性增长:链表遍历、折半之前的顺序查找改递归,数据一大就爆栈。改循环。
• 重复子问题:斐波那契的朴素递归 T(n) = T(n-1) + T(n-2) 是指数级,因为 fib(k) 被算了无数遍。这不是分治(子问题不独立,互相共享),解法是记忆化或直接递推(第 10 章动态规划的主旨就是它)。
• 需要中间状态共享:递归天然「每层一个世界」,有的算法要在遍历中维护全局计数器、修改外部结构,递归传参传得心累时,显式栈(第 3 章)+ 循环反而清爽。

尾递归(递归调用是函数最后一个动作)理论上可以被编译器优化成循环,但 C 标准不保证,只有部分编译器在 -O2 下做。把正确性押在编译器的优化开关上不职业,该迭代就迭代。

常见错误

• 忘了基线条件或基线不可达。fact(n) = n * fact(n-1) 没写 if (n <= 1) 就是无限递归,爆栈;基线判断放在递归调用之前。
• 递归深度按「调用次数」估。深度 1000 的递归每层栈帧 200 字节就是 200KB,看似安全;但每层再多开一个 4KB 的局部数组,8MB 栈瞬间见底。算深度要连栈帧体积一起算。
• 把「分治」用在子问题相关的场景。股票买卖、路径计数这类子问题互相纠缠的问题,分治只会指数爆炸,它们属于第 10 章的动态规划,分界线就是「子问题独立吗」。

练习

1. 手算:用递推式法分析 T(n) = 2T(n/2) + n 和 T(n) = T(n/2) + n,分别展开三层找规律,给出封闭形式(前者 O(n log n),后者 O(n))。
2. 实现:非递归中序遍历(显式栈),拿第 5 章 BST 的树验证输出和递归版一致;再统计两种版本在 10 万节点随机树上的耗时。
3. 动手:实现 Karatsuba 大数乘法(可用 long long 模拟「n 位整数」),在 n = 10⁵ 位时与朴素乘法对比次数,验证 3 次子乘 vs 4 次的差距。
4. 思考:汉诺塔问题的最优解是唯一的吗?证明移动次数下界 2ⁿ - 1(提示:最大的盘动一次,它上面的 n-1 个盘必须先整体挪走,递归论证)。