一、起源:自相似问题的统一表达
1.1 自相似结构:同一逻辑覆盖不同规模
有一类问题由自身的同类问题构成:
- 求 n 个数之和,等于前 n−1 个数之和加上第 n 个数;
- 求二叉树的高度,等于 1 加上左右子树高度的较大者;
- 求一个目录的总大小,等于当前目录下文件大小之和,加上各子目录总大小之和;
- 从 n 个元素中取出第 k 小的元素,可以先用一个枢轴把元素分成两半,再在其中一半里继续找。
这类问题的共同结构是自相似:整体由同类型的、规模更小的部分组成。表达同一件事有两种方式:
| 表达方式 | 代码量的增长 | 正确性的验证方式 |
|---|---|---|
| 为每个规模分别写一段代码 | 与问题规模成正比,规模不设上限时无法写完 | 逐段验证,工作量随规模增长 |
| 用一段代码同时覆盖所有规模 | 固定 | 验证最小规模与"由小规模得到大规模"两步 |
递归是后者的形式化:函数在自身的定义中调用自身,并在每次调用时收缩规模参数。它把"要处理多少种规模"这件事,压缩为"如何处理最小规模"与"如何由更小规模的结果构造当前结果"两件事。
1.2 递归与数学归纳的对应关系
递归的正确性论证与数学归纳法逐条对应:
| 数学归纳法 | 递归代码 |
|---|---|
| 基础情形:验证 P(0) 或 P(1) 成立 | 终止条件:最小规模直接给出结果 |
| 归纳假设:假设对所有 k < n,P(k) 成立 | 递归调用:直接信任子调用返回的结果,不再展开 |
| 归纳步骤:由 P(k) 推出 P(n) | 递归关系:把子问题的解组合成当前解 |
这一对应关系带来两点实践结论。
- 递归代码正确性只需检查两端。一端是终止条件是否覆盖了所有可达的最小规模,另一端是组合方式是否真的等价于原问题的定义。中间规模不需要逐个验证,这与归纳法不需要逐项验证是同一件事。
- 递归的缺陷也大多出现在这两端。终止条件缺失或边界考虑不全,表现为不终止或结果错误;组合方式写错,表现为返回值漏算或多算。二者都会在中等规模上暴露,但根因始终在两端。
归纳假设的"信任"是递归与手工展开的区别所在。代码不需要在同一处覆盖全部规模,因为每一层调用都会重新执行同一段判断逻辑。这也是递归代码通常很短的原因。
1.3 表达力强与运行代价并存
递归在表达上的优势集中在三类问题上:
- 自相似的结构化数据:树、目录、表达式、嵌套配置。定义的递归性直接映射为代码的递归性,见 二叉树与二叉搜索树。
- 分而治之的求解过程:把问题划分、分别求解、再合并,代码结构与解题思路一一对应。
- 回溯与试探:走到死路时回到上一个分叉点,天然需要保存沿途的决策现场。
代价同样明确,且与代码长度不成比例:
| 代价类型 | 来源 | 影响 |
|---|---|---|
| 调用开销 | 每次调用需压栈、传递参数、返回 | 常数因子上升,但量级不变 |
| 栈空间 | 每一层现场占用一个栈帧 | 空间随深度增长;深度受线程栈容量限制 |
| 深度上限 | 线程栈容量远小于堆容量 | 深度与数据规模同阶时会触发栈溢出 |
| 重复计算 | 相同子问题被反复求解 | 量级退化,如朴素递归斐波那契为指数级 |
前两项是常数与空间层面的代价,可以用工程手段缓解;后两项会改变可解范围,属于设计层面必须处理的问题。递归与迭代的选择、递归式与分治的复杂度分析,都是围绕这四项代价展开。从抽象数据类型的角度看,递归与分治是算法层面的组织方式,而数据结构决定了操作集合,"能做什么"与"以什么代价做"两条主线的分工见 抽象数据类型(ADT)。
二、原理
2.1 递归的三要素
2.1.1 终止条件、递归关系与状态收缩
一段可终止且正确的递归,必须同时具备三个要素:
| 要素 | 含义 | 缺失或错误的后果 |
|---|---|---|
| 终止条件 | 存在若干规模,其解可直接给出而不需要继续递归 | 不终止,最终以栈溢出结束 |
| 递归关系 | 当前规模的解可由更小规模的解组合而成 | 结果错误,或子问题与原问题不等价 |
| 状态收缩 | 每次调用后的问题规模严格小于当前规模 | 不终止;或规模不降导致代价爆炸 |
三者中,"状态收缩"最容易被忽略。终止条件存在并不保证会到达终止条件:若某条路径上参数不变化或反向变化,递归仍会一直进行。检查方式是列出每次递归调用时各参数的变化量,确认存在一个单调向终止条件推进的量。
function solve(state):
if isBaseCase(state): # 终止条件:最小规模直接求解
return baseResult(state)
sub = shrink(state) # 状态收缩:规模严格减小
return combine(solve(sub)) # 递归关系:由子问题的解构造当前解
终止条件与边界的对应关系。 终止条件的具体形态由数据结构与问题定义决定,常见的边界有三类:
- 空结构:
null引用、长度为 0 的数组或集合、空目录、空树。作用于空结构时通常返回单位元(和为 0、高度为 0、大小为 0)。 - 单元素结构:叶子节点、长度为 1 的区间、只有一个元素的集合。这类规模往往需要单独处理,因为不能再划分。
- 区间型问题的两种口径:闭区间
[l, r]与半开区间[l, r)的终止条件不同。闭区间的空区间写作l > r,半开区间的空区间写作l >= r。两种口径混用会产生空区间、单元素区间分辨不清的缺陷。
空结构与单元素结构常需分别处理。只处理其中一种时,缺陷会在特定输入形状下出现:只处理空结构,则在叶子节点上继续递归到空;只处理单元素,则在输入为空时直接访问元素而抛异常。
2.1.2 递归的两种形态:自顶向下与自底向上
同一个递归关系有两种书写方向:
| 形态 | 计算方向 | 载体 | 中间结果保存位置 |
|---|---|---|---|
| 自顶向下 | 从原问题拆解到最小规模,返回时逐层组合 | 递归调用 | 栈帧 |
| 自底向上 | 从最小规模逐层递推到原问题 | 迭代循环 | 表(数组或哈希) |
自顶向下的代码结构与问题定义一致,通常更短;自底向上把递归栈替换为显式的表,深度不受限制,代价是需要确定状态的计算顺序,且通常需要计算全部状态而不是只计算可达状态。
在树形结构上,两种形态对应两类遍历顺序:
- 自顶向下对应先序:在向下递归时携带约束或累积量(路径和、深度、上下界)。
- 自底向上对应后序:先取得子树的结果,再在根处汇总(子树大小、高度、是否平衡)。
同一问题在两种形态之间可以相互转换。转换的代价是需要明确区分"向下传递的状态"与"向上汇总的结果",这也是辅助函数参数设计的核心问题。两种形态的对照与树上递归的展开见 二叉树与二叉搜索树。
2.1.3 尾递归的含义与语言支持差异
尾递归指递归调用是当前函数的最后一步操作,且其返回值被直接返回,调用返回之后没有任何待执行的计算。
// 尾递归:递归调用是最后一步,返回后没有剩余工作
static long sumTail(int[] items, int i, long acc) {
if (i == items.length) {
return acc;
}
return sumTail(items, i + 1, acc + items[i]);
}
// 非尾递归:递归返回后还要执行加法
static long sum(int[] items, int i) {
if (i == items.length) {
return 0;
}
return items[i] + sum(items, i + 1);
}
尾递归的价值在于它可以被机械地改写为循环:当递归调用返回后没有剩余工作时,当前栈帧不再需要保留,循环变量可以承接参数与累加器的角色。上面两段代码的循环形式分别是 for 循环累加与语句顺序调换,量级相同而栈空间从 O(n) 降为 O(1)。
语言与运行时对尾调用的处理差异很大:
| 语言 / 平台 | 尾调用优化 | 说明 |
|---|---|---|
| Scheme | 规范要求 | 尾调用必须复用当前栈帧,是语言语义的一部分 |
| Kotlin | 编译期支持 | tailrec 关键字,仅对直接递归生效 |
| Scala | 编译期部分支持 | 标注 @tailrec 且为自身尾递归时编译为循环,跨方法的尾调用不保证 |
| Java / JVM | 不支持 | 字节码层面没有尾调用消除,尾递归写法仍然逐层累积栈帧 |
| Python | 不支持 | 默认递归深度上限约 1000,可调整上限但仍受真实栈空间约束 |
| C / C++ | 依编译器与优化级别 | 常见编译器在开启优化时可复用栈帧,但不属于语言保证 |
| JavaScript | 规范要求、实现普遍未落地 | 规范定义了正确尾调用,主流引擎中落地有限 |
由此得到一条设计约束:不能把"依赖尾递归优化来避免栈溢出"作为跨语言的正确性前提。在 JVM 上,形如 return f(...) 的尾递归与普通递归在栈空间上完全一致。可移植的处理方式是把尾递归手工改写为循环,或在注释中明确该写法的前提。JVM 上尾调用不被优化带来的具体表现见 栈与队列。
2.2 调用栈
2.2.1 栈帧的构成
每次方法调用发生时,JVM 在当前线程的虚拟机栈上压入一个栈帧,其内容包括:
- 局部变量表:方法的参数与方法体内的局部变量,按槽位存放;
- 操作数栈:字节码运算的中间结果,用于表达式求值;
- 动态链接:指向运行时常量池中该方法所属类的符号引用;
- 方法返回地址:调用点的位置,方法返回后从此处继续执行。
线程的虚拟机栈(向低地址方向增长)
┌────────────────────────────┐
│ 栈帧:solve(n) │ ← 栈底
│ 局部变量表 / 操作数栈 │
│ 动态链接 / 返回地址 │
├────────────────────────────┤
│ 栈帧:solve(n/2) │
│ (上一层调用留下的现场) │
├────────────────────────────┤
│ 栈帧:solve(1) │ ← 当前栈顶
└────────────────────────────┘
虚拟机栈的区域划分、与本地方法栈的合并关系、各区域可抛出的异常类型见 JVM 内存结构与垃圾回收。
由此可以直接解释递归的一个基本性质:每一层递归都拥有一份独立的局部变量与参数副本。方法参数按值传递,被调用方修改自己副本中的值不会影响调用方的副本。这正是递归依赖"参数携带状态、返回值汇总结果"而不依赖共享变量的原因,也是回溯类算法必须显式撤销状态修改的原因。
2.2.2 递归深度与栈空间的关系
递归的最大深度与线程栈容量的关系可以写成:
可承受的最大递归深度 ≈ 单线程栈容量(-Xss) / 单层栈帧大小
栈帧大小由参数与局部变量的数量与类型、对齐填充决定,通常在数十到数百字节的量级。以 -Xss 为 512KB(约 5.2×10^5 字节)、每帧约 100 字节估算,深度上限落在数千层量级。这一估算的用途是比较量级而非给出精确值:局部变量多、参数体积大的方法单帧更大,可递归的深度相应减小;把方法体中的临时变量提前释放或抽成独立方法,都可能改变单帧大小。
三条推论:
- 递归深度由数据形状决定,而非由代码决定。同一段树遍历代码,在平衡二叉树上深度为 O(log n)(平衡树把树高限制在对数级,见 平衡树:AVL 与红黑树),在退化的链式结构上深度为 O(n)。同样的实现,可承受的规模相差数个数量级。
- 递归深度与递归调用总次数无关。归并排序的递归调用总数为 2n−1 次,但同一时刻栈上的帧数只有 log₂n 层;树遍历的帧数等于当前路径的长度,与树的节点总数无关。空间复杂度由最大深度决定,这一点在 复杂度与算法分析 中有完整讨论。
- 深度是设计参数。把深度写成与输入规模同阶的表达式(如"递归深度等于链表长度"),等于把可处理的规模上限交给了
-Xss,而-Xss通常只有 MB 量级,无法通过扩大堆来改善。链表上的递归深度限制与链表归并的对数级深度做法见 数组与链表。
2.2.3 栈溢出的成因与阈值
StackOverflowError 的触发条件是:线程的虚拟机栈帧总量超过 -Xss 指定的容量。常见成因有四类:
| 成因 | 表现 | 处置方向 |
|---|---|---|
| 终止条件缺失或错误 | 深度单调增长,必然溢出,异常堆栈中同一方法反复出现 | 修正终止条件与边界 |
| 数据形状导致深度与规模同阶 | 长链表、退化树、超深目录、超长嵌套输入 | 改迭代,或改为队列驱动 |
| 单帧体积偏大 | 局部变量与参数多,同一深度更早触顶 | 拆分方法、减少局部变量 |
-Xss 偏小 | 现象与数据形状无关,调大后即消失 | 评估线程数与栈总量的权衡后调整 |
需要区分另外两种形态相近的失败:
StackOverflowError:单个线程的栈被用尽,成因是深度或单帧体积。处置方向是改迭代或调大-Xss。OutOfMemoryError: unable to create new native thread:线程数过多,导致线程栈的内存总量无法再申请。处置方向是降低并发或调小-Xss。
两者的处置方向相反,误判会把问题放大。两者的机制差别与参数对应关系见 JVM 内存结构与垃圾回收 中虚拟机栈的两种失败一节。
排查入口有两处。异常堆栈轨迹中同一方法名重复出现的段数,就是递归深度的量级;线程转储可以看到调用链的长度与形态,其判读方法见 Java 应用诊断与部署调优 中线程转储的判读一节。
2.3 递归到迭代
递归与迭代是同一算法的两种表示。改写不是"更高级的写法",而是把运行时隐式维护的调用栈换成显式的数据结构,从而改变空间的位置与深度的上限。
2.3.1 显式栈模拟
核心做法:把"待处理的问题"放入一个显式栈,循环取出并处理,处理过程中把新产生的子问题压栈。
递归栈帧中保存的信息需要在显式栈中重新表达:
| 递归中隐式保存的信息 | 显式栈中的对应物 |
|---|---|
| 还有哪些子问题未处理 | 尚未弹出的栈元素 |
| 子问题处理完后回到哪里继续 | 保存在栈元素中的状态或处理顺序 |
| 局部变量(如累积和、当前路径) | 栈元素中的字段,或循环外维护的变量 |
只需"访问一次"的场景(前序求和、连通性判断)改写最简单,栈中只存元素本身;需要"访问两次"的场景(后序处理,即子问题结果就绪后再处理父问题)必须额外保存状态。
2.3.2 状态标记法
用阶段标记区分"进入"与"返回"两次访问,是显式栈模拟后序的通用做法:
push (root, ENTER)
while stack is not empty:
(node, phase) = pop
if phase == ENTER:
push (node, EXIT) # 返回时再处理的标记
for each child in reverse order:
push (child, ENTER) # 逆序压入,弹出顺序与递归一致
else:
processAfterChildren(node) # 相当于递归调用返回后的组合步骤
阶段标记的另一种等价写法是本节点与子节点分两批入栈,或使用访问标记集合记录已完成的节点。三种写法的空间代价相近,差别在于额外的状态字段还是额外的集合。
2.3.3 尾递归改循环
有累加器参数的尾递归可以直接改写为循环,把累加器与索引提升为循环变量。非尾递归若要在不引入显式栈的前提下改写,通常需要先引入累加器把"返回后要做的工作"提前完成,这一步并不总可行:后序处理(子树先完成)无法用累加器表达,因为它要求两个子问题的结果在父节点处汇合。
2.3.4 收益与代价
| 维度 | 递归 | 迭代(显式栈) |
|---|---|---|
| 空间位置 | 线程栈,容量由 -Xss 决定,通常 MB 量级 | 堆,容量由 -Xmx 决定,可达 GB 量级 |
| 深度上限 | 数千层量级 | 由堆容量与单个元素大小决定,可达数百万 |
| 单次开销 | 方法调用(压栈、参数传递、返回) | 容器入栈出栈,通常更小,但元素为对象时开销上升 |
| 中间状态 | 局部变量天然保留 | 需要显式保存,代码量与出错面增加 |
| 可中断性 | 帧之间难以暂停与恢复 | 循环每轮都是中断点,便于暂停、限流与分片 |
| 可读性 | 与问题定义同构,通常更短 | 状态机式写法,需额外注释说明状态含义 |
结论是分工而非替代:深度可控、逻辑与问题定义同构时用递归;深度与数据规模同阶,或需要在中途暂停、恢复、限流时改用迭代。调用栈与递归展开的对应关系、树与图上改写的具体收益见 栈与队列,深度优先遍历的递归与显式栈两种实现的差别见 图的表示与遍历。
2.4 递归式与复杂度
2.4.1 递归树与逐层求和
递归算法的代价由递归式描述。最通用的求解手段是递归树:把递归式按层展开,每层各节点的代价求和,再对所有层求和。
以归并排序 T(n) = 2T(n/2) + c·n 为例:
第 0 层: c·n 代价 c·n
第 1 层: c·n/2 c·n/2 代价 c·n
第 2 层: c·n/4 c·n/4 c·n/4 c·n/4 代价 c·n
...
第 k 层:共 2^k 个节点,每个代价 c·n/2^k 代价 c·n
...
叶子层:n 个节点,每个常数代价 代价 c·n
树高为 log₂n,每层代价恒为 c·n,总代价为 Θ(n log n)。递归树方法的适用面最广,不依赖主定理的前提;当每层代价不等时,需要对求和式作出估计(等比求和、几何级数、或对上界与下界分别估计)。
2.4.2 主定理的三种情形与判断顺序
对形如 T(n) = a·T(n/b) + f(n) 的递归式(a ≥ 1、b > 1 为常数,f(n) 渐近正),判断按以下顺序进行:
- 写出三项参数:子问题个数 a、规模缩减因子 b、每次划分与合并的代价 f(n)。
- 算临界指数:
log_b a与n^(log_b a)。这是分治结构"叶子侧"的增长速度。 - 比较 f(n) 与 n^(log_b a):
- f(n) 更小且差距为多项式级别(存在 ε > 0 使 f(n) = O(n^(log_b a − ε))):叶子侧主导,T(n) = Θ(n^(log_b a));
- 两者同阶(f(n) = Θ(n^(log_b a))):每层代价相近,T(n) = Θ(n^(log_b a)·log n);
- f(n) 更大且差距为多项式级别,并满足正则条件(存在 c < 1 使 a·f(n/b) ≤ c·f(n)):根侧主导,T(n) = Θ(f(n))。
- 落入空隙或前提不成立时退回递归树或代入法。f(n) 与 n^(log_b a) 的差距不是多项式级别(如
T(n) = 2T(n/2) + n log n),或规模不成等比缩减(如T(n) = T(n−1) + f(n)),主定理不适用。
判断顺序的关键是先算临界指数再比较,而不是先判断"分几份":同一对 (a, b) 下,f(n) 的量级不同会落入不同情形。
2.4.3 常见递归结构的结论
| 结构 | 递归式 | 复杂度 | 说明 |
|---|---|---|---|
| 二分查找 | T(n) = T(n/2) + O(1) | O(log n) | 减治,每层常数代价,深度 log₂n |
| 二分求幂 | T(k) = T(k/2) + O(1) | O(log k) | k 为指数,与二分查找同构 |
| 归并排序 | T(n) = 2T(n/2) + O(n) | O(n log n) | 合并代价线性,主定理情形二 |
| 快速排序(平均) | T(n) = T(n/3) + T(2n/3) + O(n) | O(n log n) | 划分近似均衡,规模不成等比 |
| 快速排序(最坏) | T(n) = T(n−1) + O(n) | O(n²) | 每次划分只减少一个元素 |
| 二叉树遍历 | T(n) = T(k) + T(n−1−k) + O(1) | O(n) | 每节点常数处理,与树形无关 |
| 朴素递归斐波那契 | T(n) = T(n−1) + T(n−2) + O(1) | O(φⁿ) ≈ O(1.618ⁿ) | 重复子问题导致指数级 |
| 记忆化斐波那契 | 每个子问题只算一次 | O(n) | 时间换空间 |
| 汉诺塔 | T(n) = 2T(n−1) + O(1) | O(2ⁿ) | 规模按相减缩减,主定理不适用 |
| 插入排序 | T(n) = T(n−1) + O(n) | O(n²) | 减治,深度为 n |
| Karatsuba 乘法 | T(n) = 3T(n/2) + O(n) | Θ(n^1.585) | log₂3 ≈ 1.585 |
| Strassen 矩阵乘法 | T(n) = 7T(n/2) + O(n²) | Θ(n^2.807) | log₂7 ≈ 2.807 |
主定理的完整适用边界、递归树的分层展开方式、代入法的步骤、渐近记号的用法与常见误用,见 复杂度与算法分析。此处只强调与递归、分治直接相关的两点:
- 同一个递归结构可能对应多个递归式。快速排序的递归式取决于划分质量,平均与最坏的结论相差一个量级,因此结论必须标注分析对象。
- 深度与代价是两个维度。汉诺塔的递归深度为 n,代价为 O(2ⁿ),二者不同阶;快速排序平均深度为 O(log n),最坏深度为 O(n)。
2.5 分治法
2.5.1 三个步骤
分治法把问题的求解拆成三步:
- 划分(divide):把原问题划分为若干个规模更小、类型相同的子问题。
- 解决(conquer):递归求解各子问题;当子问题规模足够小时直接求解,不再继续划分。
- 合并(combine):把子问题的解组合成原问题的解。
三步结构对应递归式的三个部分:划分方式决定子问题的个数 a 与规模 n/b,直接求解的规模决定递归深度,合并方式决定每层代价 f(n)。
2.5.2 适用条件
三项条件需要同时满足:
| 条件 | 含义 | 不满足时的后果 |
|---|---|---|
| 子问题相互独立 | 子问题之间没有共享的状态或重复的子问题 | 存在重叠子问题时朴素分治会重复计算,应改为记忆化或自底向上的递推,见 动态规划 中重叠子问题一节 |
| 规模确实缩小 | 每次划分得到的子问题规模严格小于原问题 | 规模不降则递归不终止,或层数失去控制 |
| 合并代价可控 | 合并的代价不高于分治节省的代价 | 合并代价过大时整体退化到与朴素解法同阶,分治失去意义 |
第三条最容易被低估。若每层的合并代价为 O(n²),则 T(n) = 2T(n/2) + O(n²) 的结论是 O(n²),与"直接在原问题上两两比较"同阶。此时分治只增加了递归与临时空间的成本,没有换来量级收益。判断标准是:分层处理的每层代价乘上层数,是否小于朴素解法的代价。
2.5.3 分治与减治的区别
| 维度 | 分治(divide and conquer) | 减治(decrease and conquer) |
|---|---|---|
| 递归的子问题个数 | 通常不少于 2 | 1 |
| 递归式形态 | T(n) = a·T(n/b) + f(n),a ≥ 2 | T(n) = T(n/b) + f(n) 或 T(n) = T(n−1) + f(n) |
| 递归深度 | log_b n | 按规模相除时为 log_b n,按规模相减时为 n |
| 是否需要合并步骤 | 需要,合并代价是主要成本之一 | 不需要,子问题的解即原问题的解 |
| 典型实例 | 归并排序、最近点对、大整数乘法、快速选择 | 二分查找、二分求幂、插入排序、多数单变量求根 |
区分两者的实际意义在于复杂度结论的推导方式。减治的递归式中 a = 1,主定理的情形二会给出 Θ(n^(log_b 1)·log n) = Θ(log n),这一结论只在规模按相除缩减时成立;规模按相减缩减(T(n) = T(n−1) + f(n))的递归式主定理不适用,需要逐层展开。
2.5.4 平衡划分原则与合并代价的权衡
分治的效率由两个因素共同决定,它们的作用位置不同:
- 划分的平衡程度决定递归深度。平衡划分(
T(n) = 2T(n/2)) 的深度为 log₂n;极端不平衡(T(n) = T(1) + T(n−1)) 的深度为 n,整体退化为 O(n²)。快速排序在有序输入上退化为 O(n²),正是划分不平衡的直接后果。 - 合并代价决定每层开销。每层代价为 O(n) 时总代价为 O(n log n);每层代价为 O(n²) 时总代价为 O(n²),此时划分是否平衡已不改变量级。
由此得到两条设计原则:
- 尽量使划分均衡。均衡划分让"每层子问题的总规模"保持与原问题同阶,层数才是 log 量级。随机化枢轴、取中位数作为枢轴、按重心分解树,都是把划分推向均衡的手段。
- 把工作放在划分阶段而不是合并阶段,或反之。快速排序把代价集中在划分(原地划分 O(n)),合并步骤为空;归并排序把代价集中在合并(线性合并),划分只需取中点。两者都只让一侧承担线性代价,因此都是 O(n log n)。若划分与合并都做线性以上的工作,量级就会被抬高。
2.6 经典分治问题
2.6.1 归并排序
- 划分:取中点把区间分为两半;
- 解决:递归排序两半,直到区间长度为 1(此时天然有序);
- 合并:用两个指针顺序扫描两段有序区间,按序写入辅助数组。
递归式 T(n) = 2T(n/2) + O(n),结论 O(n log n)(最坏与平均相同)。空间上需要等长辅助数组,为 O(n),属于非原地排序;链表实现不需要辅助数组,空间仅为递归栈的 O(log n)。归并排序稳定,且合并过程是顺序扫描,缓存行为友好。
2.6.2 快速排序
- 划分:选定枢轴,原地交换使小于枢轴的元素在左、大于的在右,返回枢轴位置;
- 解决:递归处理枢轴左右两个子区间;
- 合并:无,划分完成后元素已就位。
划分代价为 O(n),代价集中在划分阶段;子问题的规模由枢轴的位置决定。
| 输入情形 | 递归式 | 复杂度 |
|---|---|---|
| 划分近似均衡 | T(n) = T(n/3) + T(2n/3) + O(n) | O(n log n) |
| 每次划分只减少一个元素 | T(n) = T(n−1) + O(n) | O(n²) |
避免退化的手段是改善枢轴选择:随机取枢轴、三数取中、或在划分极不平衡时切换到堆排序(内省排序)。快速排序的空间复杂度为递归栈深度:平均 O(log n),最坏 O(n),因此在小规模区间切换插入排序、先递归较小区间再循环处理较大区间(尾递归消除),都能把栈深度压到 O(log n)。三种 O(n log n) 排序在常数、稳定性与空间上的对照见 堆与优先队列 中与快速排序、归并排序的对比一节;两者的分区写法(Lomuto 与 Hoare、三路分区)、稳定性处理与最坏情况的工程缓解见 排序与查找 中分治排序一节。
2.6.3 二分查找与快速幂(减治)
二分查找每次比较后只在一个子区间中继续:
T(n) = T(n/2) + O(1) → O(log n)
成立的前提有两条:序列有序(比较结果能确定目标所在的一侧),以及中点可 O(1) 到达(按下标随机访问)。
快速幂把指数二分,只处理一个规模减半的子问题:
static long power(long base, long exp) {
if (exp == 0) {
return 1; // 终止条件
}
long half = power(base, exp / 2); // 只递归一个子问题
return (exp % 2 == 0) ? half * half : half * half * base;
}
T(k) = T(k/2) + O(1) → O(log k) (k 为指数)
两者都属于减治:不需要合并步骤,子问题的解经常数级变换即为原问题的解。同一模式可推广到矩阵快速幂、大整数乘法的幂运算与线性递推的加速求解。
2.6.4 最近点对
暴力解法需要考察全部点对,代价为 O(n²)。分治的做法:
- 划分:按 x 坐标排序后取中线,把点集分为左右两半;
- 解决:递归求左右两半内部的最近点对距离,取较小者 d;
- 合并:只需检查跨越中线的点对,且只需检查横坐标距中线不超过 d 的条带区域;条带内的点按 y 坐标排序后,每个点只需与后续常数个点比较。
递归式(若预处理阶段已完成按 x 与按 y 的排序)为 T(n) = 2T(n/2) + O(n),结论 O(n log n)。若每一层都重新排序,则每层代价为 O(n log n),总代价升为 O(n log²n)。
该问题的价值在于它展示了合并代价的控制方式:合并阶段检查的候选对数量必须被几何性质限制为常数级,否则合并退化为 O(n²)。条带宽度取 d、条带内按 y 排序后比较常数个点,这两条约束缺一不可。
2.6.5 大整数乘法与矩阵乘法
Karatsuba 乘法把 n 位整数乘法拆为 3 次 n/2 位乘法(而非按位拆分的 4 次):
T(n) = 3T(n/2) + O(n) → Θ(n^(log₂3)) = Θ(n^1.585)
Strassen 矩阵乘法把 n 阶矩阵乘法所需的 8 次 n/2 阶乘法减为 7 次:
T(n) = 7T(n/2) + O(n²) → Θ(n^(log₂7)) = Θ(n^2.807)
两者共同的设计思路是减少子问题的个数 a:a 出现在临界指数 log_b a 上,降低 a 直接降低整体量级,这比优化合并的常数因子更有效。代价同样明确:中间项增多导致常数因子上升,数值稳定性下降,递归带来的临时空间与深度需求增加。因此实际实现会在规模低于某个阈值时切回朴素算法,这一取舍与"小规模下常数因子主导"是同一原理。
作为对照,朴素方法对应 T(n) = 4T(n/2) + O(n)(log₂4 = 2,结论 Θ(n²))与 T(n) = 8T(n/2) + O(n²)(log₂8 = 3,结论 Θ(n³)),即按定义逐块计算的多项式量级。
2.6.6 快速选择(Top K)
在无序数组中找第 k 小的元素,不需要完全排序。做法是借用快速排序的划分,但只递归包含目标元素的那一侧:
平均:T(n) = T(n/2) + O(n) → O(n)(期望)
最坏:每次划分只减少一个元素 → O(n²)
平均代价为线性,原因是每次划分后问题规模减半,而划分代价为线性。最坏情况与快速排序同源,来自枢轴选择的极端不平衡;使用中位数的中位数(BFPRT)选择枢轴可以保证划分平衡,从而得到最坏 O(n),代价是常数因子显著上升。
与"用大小为 K 的反向堆维护 Top K"(O(n log K))的取舍在于:前者要求数据可随机访问且可反复比较,只求第 k 个元素的值时最优;后者适用于流式数据与 K 远小于 n 的场景,且能同时保留 K 个结果。两种方案的对照与实现见 堆与优先队列 中 Top K 一节。
2.6.7 树形分治与点分治
树本身是递归定义的,因此树上的分治有两种形态:
- 按子树的自然划分:把问题交给各子树递归求解,在根处合并,递归式为
T(n) = Σ T(n_i) + f(n)。当树平衡时深度为 O(log n);当树退化为链时深度为 O(n),与链表上的递归同源。区间上的线段树是这一形态的存储化实现:以区间为节点二分,要求合并运算满足结合律,才能任意切割区间并按任意顺序合并,见 线段树与并查集。 - 按重心分解(点分治):用于树上路径类问题。每次选取当前连通块的重心(使最大子树规模不超过总规模一半的节点)作为分治中心,统计经过该中心的路径,再对去掉中心后得到的各个连通块递归处理。
重心保证了递归深度为 O(log n):每次分解后最大连通块的规模不超过原规模的一半。若每层的统计代价为 O(n),则总代价为 O(n log n)。点分治在实现上需要处理一个容易出错的点——合并阶段的去重:统计"经过中心的路径"时,同一子树内部的路径会被重复计入,必须按子树分别统计并从总数中扣除,这一容斥步骤的正确性依赖于"路径是否经过中心"这一划分,与分治法"子问题相互独立"的要求直接对应。
2.7 递归与记忆化
重叠子问题指朴素递归在同一参数组合上被多次求解。以斐波那契为例:
T(n) = T(n−1) + T(n−2) + O(1) → O(φⁿ) ≈ O(1.618ⁿ)
递归树中同一个 T(k) 会被反复展开,子问题数量随 n 指数增长的根源不是"分成了两个子问题",而是"两个子问题高度重叠"。当子问题的个数是多项式级(如 n 个不同的 k)而递归树是指数级时,缓存每个子问题的解可以把代价降到"子问题个数 × 单个子问题的代价"。重叠子问题是分治与动态规划的分界线:子问题独立时用分治,子问题重叠时用记忆化或递推。状态的定义方式与转移方程的构造、两种实现方式的相互转化见 动态规划 中记忆化与递推一节。
两种消除重复计算的方式:
| 维度 | 记忆化(自顶向下) | 递推(自底向上) |
|---|---|---|
| 计算范围 | 只计算从原问题可达的状态 | 计算全部状态 |
| 递归栈 | 保留递归结构,有深度风险 | 无递归,无深度风险 |
| 依赖顺序 | 无需显式确定,缓存未命中时继续递归 | 必须按依赖顺序填表,顺序错误会取到未计算的值 |
| 空间优化 | 难以压缩(依赖访问顺序不确定) | 可用滚动数组把高维表格压到线性空间 |
| 常数开销 | 缓存查找 + 方法调用 | 循环开销,通常更小 |
| 适用场景 | 状态空间稀疏、边界条件复杂、递推方向不直观 | 状态空间稠密、依赖顺序清晰 |
两者的结论相同(同一递推关系的两种计算顺序),差别集中在栈空间与访问模式上。选择依据是状态空间是否稠密、是否要求无栈深风险,以及是否需要空间压缩。记忆化的缓存载体按状态是否可编码为连续整数选择:可编码时用数组,状态是复合结构或不连续时用哈希表,其查找代价的期望与最坏分析见 散列表。
需要注意,记忆化解决的是重复计算,不解决深度:自顶向下的记忆化递归仍保留递归调用链,深度由依赖链长度决定。在依赖链可能很长(例如按规模逐项递减的递推)时,即使时间上已被压缩到线性,也可能因深度触顶而失败,此时应改为自底向上的递推。
2.8 工程视角
2.8.1 递归在业务代码中的常见位置
| 场景 | 递归的结构 | 深度特征 |
|---|---|---|
| 树形结构(分类、菜单、评论、部门) | 自底向上汇总,或自顶向下携带上下文展开 | 由层级数决定,通常十几到几十层 |
| 目录与文件遍历 | 目录树递归 | 由目录深度决定,可能很深且不受应用控制 |
| 审批层级与组织架构 | 沿上级链上溯,或按子树下钻 | 通常较浅,但可能出现长链(兼岗、历史数据异常) |
| 表达式、JSON、HTML、YAML 解析 | 递归下降 | 由嵌套深度决定;输入来自外部时深度不可控 |
| 依赖与连通性判断 | 深度优先 | 由路径长度决定,需要访问标记避免重复与死循环 |
| 决策与回溯类求解 | 深度优先搜索树 | 深度与决策步数同阶 |
2.8.2 深度不确定时的风险
三类风险的共同点是深度不由代码决定:
- 数据形状退化。同一段树遍历代码,遇到退化链表形结构时深度等于节点数。这类数据往往来自历史遗留、批量导入或异常写入,测试环境难以覆盖。
- 外部输入可控。解析外部数据时,嵌套深度由输入决定。嵌套 JSON、超长表达式、深层 XML 都可以构造出足以触发栈溢出的深度,这类问题同时也是可用性风险。
- 规模增长。当前数据深度只有几层,但随着业务演进可能增长;递归深度与规模线性相关的设计,其可承受上限被
-Xss固定,无法通过扩大堆解决。
与这三类风险对应的处理不是"把 -Xss 调大"(它只抬高阈值且挤压线程数),而是在设计阶段就把深度纳入约束:显式限制深度、把可能深的结构改为迭代、或对输入设置嵌套层数上限。
2.8.3 递归改迭代或队列驱动的选择依据
| 需求 | 结构 | 峰值空间的决定因素 |
|---|---|---|
| 深度优先顺序,深度可控 | 递归 | 深度 × 栈帧 |
| 深度优先顺序,深度不可控 | 显式栈 | 深度 × 元素大小(占用堆) |
| 按层或按批处理 | 队列(广度优先式) | 最大宽度 × 元素大小 |
| 子结果先就绪再处理父节点(后序) | 递归,或显式栈 + 状态标记 | 深度 × 元素大小 |
选择的依据有三条:
- 顺序语义:深度优先要求"沿一条路径走到底",栈(或递归)与之同构;广度优先要求"先处理近的、再处理远的",队列与之同构。遍历容器的选择依据与两种顺序的对应关系见 栈与队列 与 图的表示与遍历。
- 内存峰值由深度还是宽度决定:很深的窄结构用递归或栈,占用随深度增长;很宽但很浅的结构用队列,占用随宽度增长,可能远大于深度。两种结构混合时要按实际数据分布判断哪一侧更大。
- 是否需要横向聚合:需要按层统计(每层节点数、层次编号)或批量提交(一次处理同一层)时,队列天然提供分层信息——同一层的元素在队列中连续。
三、实现
3.1 递归实现要点
3.1.1 终止条件与边界
终止条件需按数据结构逐一列举,而不是凭直觉只写一种:
| 输入形态 | 处理方式 |
|---|---|
null 引用 / 空集合 / 空目录 | 返回单位元(0、空列表、true) |
| 单元素(叶子、长度 1 的区间) | 直接返回该元素的解,不再划分 |
| 区间型问题的空区间 | 明确开闭口径:闭区间为 l > r,半开区间为 l >= r |
| 单元素的区间划分 | 防止划分产生与原区间相同的子区间(死循环) |
检查方式是针对每个参数确认:所有可能到达的最小规模,是否都有一个分支直接返回。区间型问题还要确认划分后两个子区间都严格小于原区间,否则递归不终止。
3.1.2 参数与返回值设计
递归参数设计围绕两件事:向下传递什么,向上汇总什么。
- 向下传递的约束或累积量:允许范围(上下界)、当前深度、当前路径、已累积的和。这类信息在自顶向下的形态中作为参数传入。
- 向上汇总的结果:子树大小、子树高度、是否满足条件、以及需要同时返回多个值时的组合对象。这类信息通过返回值传出。
- 原方法签名不足以承载递归参数时,引入私有辅助方法,由公开方法完成参数初始化与结果提取,避免把内部递归参数暴露给调用方。
- 返回多个值时优先返回组合对象,而不是用共享字段。用可变字段汇总结果会引入隐式状态:同一份代码在多线程下不安全,且难以在测试中隔离。确需共享容器(如收集所有匹配节点)时,把它作为参数显式传入,使副作用在调用点上可见。
// 向上汇总多个值:返回组合结果,不使用共享字段
private static final class Info {
final int height; // 子树高度
final boolean balanced; // 子树是否平衡
Info(int height, boolean balanced) {
this.height = height;
this.balanced = balanced;
}
}
private static Info check(Node node) {
if (node == null) {
return new Info(0, true); // 空结构的终止条件
}
Info left = check(node.left); // 自底向上:先取得子树结果
Info right = check(node.right);
int height = Math.max(left.height, right.height) + 1;
boolean balanced = left.balanced && right.balanced
&& Math.abs(left.height - right.height) <= 1;
return new Info(height, balanced);
}
该写法把"高度"与"是否平衡"两个结果合并为一次遍历,避免了"对每个节点各求一次高度"造成的 O(n²) 重复计算。
3.1.3 剪枝与提前返回
- 结果已确定时立即返回:找到目标、当前分支已不满足约束、剩余规模不足以产生影响时,都不需要继续递归。回溯的搜索树模型、剪枝策略与状态撤销的对称性见 贪心与回溯。
- 剪枝的正确性依赖单调性:只有当"当前状态不满足条件"能推出"其所有后继状态也不满足"时,剪枝才是安全的。缺少单调性保证的剪枝会漏解。
- 把低成本判断放在前面:先判断最容易排除的条件,减少深入递归的次数;这与在循环中把开销小的条件前置是同一种优化。
3.2 递归转迭代示例
3.2.1 二叉树遍历的迭代化
三种遍历的迭代实现都用显式栈,差别在于压栈时机与访问时机:
// 前序:访问后先压右、再压左(弹出顺序与递归一致)
public static List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.add(node.value); // 进入即访问
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
// 中序:沿左链一路压栈,弹出即访问,然后转向右子树
public static List<Integer> inorder(Node root) {
List<Integer> result = new ArrayList<>();
Deque<Node> stack = new ArrayDeque<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current); // 左链全部入栈,暂不访问
current = current.left;
}
current = stack.pop();
result.add(current.value); // 左子树处理完后访问本节点
current = current.right;
}
return result;
}
中序的迭代写法不需要状态标记,因为"访问时机"恰好等于"出栈时机"。后序要求"左右子树都处理完再访问节点",出栈时无法直接判断子节点是否已处理,因此需要状态标记法或双栈法:
// 后序:状态标记法,每个节点入栈两次,第二次出栈时才访问
private static final class Frame {
final Node node;
final boolean expanded; // false 表示尚未展开子节点
Frame(Node node, boolean expanded) {
this.node = node;
this.expanded = expanded;
}
}
public static List<Integer> postorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<Frame> stack = new ArrayDeque<>();
stack.push(new Frame(root, false));
while (!stack.isEmpty()) {
Frame frame = stack.pop();
if (frame.expanded) {
result.add(frame.node.value); // 子节点已处理完,访问本节点
continue;
}
stack.push(new Frame(frame.node, true));
if (frame.node.right != null) {
stack.push(new Frame(frame.node.right, false));
}
if (frame.node.left != null) {
stack.push(new Frame(frame.node.left, false));
}
}
return result;
}
三种写法的空间复杂度都是 O(h)(h 为树高),但空间位置从线程栈转移到堆。树遍历的递归与非递归对照、以及不改动指针的莫里斯遍历见 二叉树与二叉搜索树。
3.2.2 快速排序的手写栈
把待排序的区间作为栈元素,循环取出区间完成划分并压入产生的子区间。栈深由压栈顺序决定:
public static void quickSort(int[] a) {
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[] {0, a.length - 1});
while (!stack.isEmpty()) {
int[] range = stack.pop();
int left = range[0];
int right = range[1];
if (left >= right) {
continue; // 空区间与单元素区间:不再划分
}
int p = partition(a, left, right); // 划分,返回枢轴位置
// 先压较大区间、后压较小区间:较小者先出栈被处理,
// 栈中待处理的区间规模逐次减半,栈深保持 O(log n)
if (p - 1 - left > right - (p + 1)) {
stack.push(new int[] {left, p - 1});
stack.push(new int[] {p + 1, right});
} else {
stack.push(new int[] {p + 1, right});
stack.push(new int[] {left, p - 1});
}
}
}
private static int partition(int[] a, int left, int right) {
int pivot = a[right]; // 简化写法,实际实现建议随机化枢轴
int i = left;
for (int j = left; j < right; j++) {
if (a[j] < pivot) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
}
}
int tmp = a[i];
a[i] = a[right];
a[right] = tmp;
return i;
}
压栈顺序是这一实现的关键:先压较大区间、后压较小区间,使较小区间先出栈、被优先处理,保留在栈中的区间规模按等差递减,栈深为 O(log n)。若固定先压右区间再压左区间(等价于优先递归左半),在划分极不平衡的输入上栈深会达到 O(n),把递归版本的栈溢出问题原样搬到了显式栈上——此时溢出形式上不再出现,但堆占用按线性增长。
3.2.3 目录遍历改为队列驱动
// 广度优先:按目录层级逐层处理,峰值内存由单层宽度决定
public static List<Path> walkBreadthFirst(Path root) {
List<Path> result = new ArrayList<>();
Queue<Path> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
Path dir = queue.poll();
try (DirectoryStream<Path> stream = Files.newDirectoryStream(dir)) {
for (Path entry : stream) {
result.add(entry);
if (Files.isDirectory(entry)) {
queue.offer(entry); // 子目录入队,稍后处理
}
}
} catch (IOException e) {
result.add(null); // 实际实现应记录失败目录并继续
}
}
return result;
}
改写带来三点差别:
- 深度不再受限。递归版本的深度等于目录深度,队列版本的循环层数恒为 1,目录深度再大也不影响栈;代价是队列长度可能随目录宽度增长。
- 顺序改变。队列给出的是广度优先顺序(按层级),递归给出的是深度优先顺序。若业务依赖"先处理完一个子目录再处理下一个",队列版本需要额外记录层级并按层处理。
- 不适用于需要子结果先就绪的汇总。计算每个目录的总大小要求子目录先计算完成,广度优先无法保证这一点;此时应使用显式栈加状态标记(后序),或拆成两阶段:第一遍收集全部目录,第二遍按深度从深到浅聚合。
3.3 分治实现要点
3.3.1 划分与合并的代码结构
分治的代码骨架固定,差异集中在 isSmall 的阈值、divide 的划分方式与 combine 的合并方式:
function solve(problem):
if isSmall(problem): # 规模足够小,直接求解
return baseSolve(problem)
parts = divide(problem) # 划分
results = collect(solve(p) for p in parts) # 递归求解
return combine(results) # 合并
三个实现要点:
- 小规模阈值不应省略。规模很小(常见为 1 到几十个元素)时,划分与合并的固定开销大于收益,直接求解更快;阈值也是递归的终止条件。
- 划分方式决定子问题规模是否均衡。取中点、取中位数、按重心选取,都是为了让各子问题规模接近。
- 合并函数的参数与顺序要与划分一致。划分产生 parts 的顺序、合并消费 results 的顺序需要对应,否则结果错位;这一缺陷在子问题个数为 2 时可能因对称而掩盖,在个数更多时暴露。
3.3.2 临时空间与原地操作的取舍
| 做法 | 空间 | 代价 |
|---|---|---|
| 归并式:合并时写入辅助数组再复制回原数组 | O(n) | 需要额外空间与数据复制;稳定 |
| 原地划分式(快速排序) | O(log n)(递归栈) | 不稳定;划分逻辑更易写错 |
| 复用预分配的辅助数组 | O(n),但只分配一次 | 避免每层重新分配,需要保证递归调用不交叉使用同一块缓冲区 |
两点细节值得注意:
- 归并的辅助数组应预分配并复用。在每层递归内
new一个辅助数组会把分配次数提到 O(n) 次,分配量之和仍为 O(n log n) 级别,显著放大 GC 压力。 - 原地操作并不总是空间更优。原地划分节省了辅助数组,但快速排序的空间来自递归栈;在划分不平衡时栈深为 O(n),反而超过归并排序的 O(log n) 栈深。空间比较必须把递归栈计入,口径问题见 复杂度与算法分析 中空间复杂度一节。
3.3.3 并行分治的可行性与代价
分治的结构天然适合并行:子问题独立是前提,递归调用可以分配给不同线程。可行性的判断依据是三条:
- 子问题相互独立。存在共享可变状态(同一个结果容器、同一块缓冲区)时,要么消除共享(各子问题返回局部结果,最后合并),要么加同步,后者通常抵消收益。
- 合并步骤满足结合律或顺序无关。合并运算满足结合律时,各分片的局部结果可以按任意顺序合并;不满足时并行会改变结果,例如依赖元素顺序的"首个满足条件的元素"这类查询无法直接并行。
- 任务粒度足够粗。任务拆分、提交与结果同步都有固定开销,规模降到某个阈值以下应转串行执行。阈值过小会导致线程调度开销主导,并行反而更慢。
实现方式有两类:显式的任务框架(Fork/Join 的工作窃取,把子问题提交为任务并在合并前等待)、以及由库封装的并行流(trySplit 切分数据源,各分片的结果由合并函数汇总)。后者的切分能力取决于数据源的结构,切分不均会导致部分线程空闲,相关的拆分策略与适用条件见 Java 函数式编程与 Stream 中拆分与合并策略一节;线程池的机制与饱和风险见 Java 并发编程。
并行带来的额外代价需要一并计入结论:线程调度与上下文切换、结果同步(等待子任务完成)、共享数据的可见性与伪共享、以及并行度不足时的资源闲置。因此并行分治的收益判断与串行优化一致——先确认串行路径已无更优量级,再考虑并行。
3.4 复杂度分析示例
3.4.1 用递归树逐步求解
例一:归并排序的合并代价。T(n) = 2T(n/2) + O(n)。每层节点总规模为 n,单层代价 c·n;层数为 log₂n;总代价 c·n·log₂n,即 Θ(n log n)。
例二:划分不等但均衡。T(n) = T(n/3) + T(2n/3) + O(n)。每层各节点规模之和仍为 n,单层代价 c·n;深度由最长路径决定,为 log_{3/2} n;总代价 Θ(n log n)。结论与均衡二分相同,说明只要划分比例固定且两侧都小于原规模,量级就不变,差别只在常数。
例三:合并代价过高。T(n) = 2T(n/2) + O(n²)。临界指数为 1,f(n) = n² 高于 n^1 且为多项式级别,落入主定理情形三,结论 Θ(n²)。用递归树核对:顶层代价 c·n²,逐层减半,几何级数求和收敛到 O(n²),根节点代价主导。此时分治与"直接两两比较"同阶。
例四:规模按相减缩减。T(n) = T(n−1) + O(n)。规模不成等比,主定理不适用;逐层展开得 c·(n + (n−1) + … + 1) = Θ(n²)。递归树呈链状,层数为 n 而非 log n。
3.4.2 用主定理逐步求解
判断流程以 T(n) = 9T(n/3) + n 为例:
1. 三项参数:a = 9,b = 3,f(n) = n
2. 临界指数:log_b a = log₃9 = 2,n^(log_b a) = n²
3. 比较:f(n) = n 与 n² 相比更小,且差距为多项式级别(n = O(n^(2−ε)),取 ε = 1)
4. 情形一:T(n) = Θ(n^(log_b a)) = Θ(n²)
同样流程用于 T(n) = 2T(n/2) + n:a = 2、b = 2,临界指数 log₂2 = 1,f(n) = n 与 n¹ 同阶,落入情形二,结论 Θ(n log n)。
落在空隙的例子是 T(n) = 2T(n/2) + n log n:临界指数为 1,f(n)/n¹ = log n,虽大于 n¹ 但不是多项式级别地大(不存在 ε > 0 使 f(n) = Ω(n^(1+ε))),既非情形二也非情形三;用递归树逐层求和,每层代价为 c·n·(log n − 层号),求和后为 Θ(n log²n)。
3.4.3 常见误用
| 误用 | 表现 | 纠正 |
|---|---|---|
| 忽略合并代价 | 认为"每次把问题减半就是 O(log n)" | 每层的划分与合并代价必须计入 f(n);只有减治且每层代价为常数时才是 O(log n) |
| 把减治的递减形式套用主定理 | 对 T(n) = T(n−1) + O(n) 用主定理得出错误结论 | 主定理要求规模成等比缩减;相减形式退回递归树展开 |
| 忽略取整与常数 | 认为 n 非 2 的幂时 log 结论失效 | 取整只改变常数;结论不变,但实现的区间划分需要处理不等长 |
| 只统计调用次数不统计深度 | 认为归并排序调用了 2n−1 次所以需要 O(n) 栈 | 空间由最大深度决定,归并排序栈深为 O(log n) |
| 假设划分总是均衡 | 用平均结论替代最坏结论 | 给出最坏界,或引入随机化使最坏情况的概率可忽略 |
| 小规模下仍套用量级结论 | "O(n log n) 优于 O(n²)",但在 n 很小时实测相反 | 设置切换阈值,按目标规模而非量级排名选型 |
量级结论与实测差异的完整来源见 复杂度与算法分析 中理论与实测的差异一节。
3.5 常见陷阱与排查
| 现象 | 可能原因 | 验证与处置 |
|---|---|---|
抛出 StackOverflowError,堆栈中同一方法反复出现 | 终止条件缺失或错误;边界输入未覆盖;状态未收缩 | 确认所有最小规模都有直接返回分支;列出每次调用的参数变化,确认单调逼近终止条件 |
| 数据规模不大却出现栈溢出 | 数据形状退化(长链表、退化树、超深目录);单帧体积大 | 打印结构的实际深度;评估最坏深度;改为显式栈迭代或队列驱动 |
| 递归耗时随规模指数增长 | 存在重叠子问题,同一参数被反复求解 | 统计相同参数的出现次数;改为记忆化或自底向上的递推 |
| 结果偏小、遗漏部分数据 | 返回值未在所有分支汇总;合并时漏掉某个子问题;区间开闭口径不一致 | 检查每个分支是否都有返回值;用小规模(n = 1、2、3)手工推演一遍;统一区间口径 |
| 快速排序在特定数据上退化为 O(n²) | 输入已有序或接近有序,且枢轴固定取首元素或末元素 | 随机化枢轴或三数取中;对极端不平衡的划分设置切换策略(如转堆排序) |
| 排序或分组结果不稳定,相等元素的相对顺序改变 | 分治的合并方式破坏原顺序(如原地划分、跨区间交换) | 需要稳定语义时选用归并式合并;把稳定性要求写进接口约定 |
| 回溯结果出现重复或互相污染 | 递归之间共享了可变状态,回溯时未恢复现场 | 把共享状态改为参数传递;若必须共享,在递归返回后显式撤销修改 |
| 并发分治结果不正确或偶发丢失 | 多个子任务写入同一个容器或缓冲区;合并过程缺少同步 | 各子任务返回局部结果、最后统一合并;确认合并运算满足结合律 |
| 并行分治反而更慢 | 任务粒度过细、数据源切分不均、共享资源争用 | 提高串行阈值;检查数据源的可切分性;对比单线程基线的实测数据 |
| 依赖尾递归优化而未生效 | 目标运行时不做尾调用消除(如 JVM) | 手工改写为循环;不把尾调用优化作为跨语言的正确性前提 |
排查这类问题的一个通用手段是打印深度与调用次数:在递归入口记录当前深度并统计相同参数的出现次数,前者定位栈溢出风险,后者定位重复计算。这两个量在正常规模下就能暴露设计缺陷,不必等到线上出现栈溢出。
3.6 检查清单与工程替代
3.6.1 递归代码评审要点
终止条件与边界。
- 终止条件是否覆盖了所有可达的最小规模(空结构与单元素结构是否分别处理)。
- 区间型问题的开闭口径是否统一,空区间与单元素区间的判断是否写了同一个分支。
- 每次递归调用后,是否存在一个单调逼近终止条件的量;该量是否可能因取整而停滞(如整数除法把 1 变成 0 后不再减小)。
递归关系与返回值。
- 每个分支是否都有返回值,合并是否覆盖全部子问题。
- 递归参数中的共享可变对象是否在返回后被显式撤销。
- 返回多个值时是否使用了组合对象而非共享字段;辅助方法的职责划分是否清晰。
深度与重复计算。
- 最大递归深度是否可估计;最坏输入下的深度是多少;该深度与
-Xss的量级关系如何。 - 是否存在重复子问题;相同参数是否会被多次求解;是否应引入记忆化。
- 深度是否与输入规模线性相关;若相关,输入规模是否受控。
运行时前提。
- 是否依赖尾调用优化;目标运行时是否真的提供该优化。
- 是否在多线程环境下共享递归产生的状态。
3.6.2 何时应改用迭代或队列驱动
满足以下任一条时,应把递归改写为显式栈的迭代或队列驱动的处理:
- 深度与输入规模线性相关,且规模不受代码控制(链表、退化树、外部输入的嵌套深度)
- 已出现或按最坏深度估算会出现的
StackOverflowError - 需要在遍历中途暂停、恢复、分片或限流:帧之间无法保存中间状态,而循环的每一轮都是自然的边界
- 需要按层或按批处理:队列天然携带层次信息
- 需要控制内存峰值的位置:把占用从线程栈(
-Xss,不可扩容)转移到堆(-Xmx,可扩容) - 深度受
-Xss挤压而无法通过其他手段缓解,且调大-Xss会与线程数冲突
反向的判据同样成立:深度可控、逻辑与问题定义同构、且不需要中断时,递归的可读性优势更大,不应为规避一个不存在的深度风险而增加状态机式代码。
3.6.3 深度保护与限流
深度保护的做法分三层,从代码到配置:
| 层次 | 做法 | 要点 |
|---|---|---|
| 代码内显式校验 | 递归入口检查当前深度,超过上限立即返回错误或降级结果 | 上限应作为配置项而非魔法数字;错误信息中带上当前深度 |
| 输入侧约束 | 对嵌套类输入设置最大层数,解析外部数据前先做深度预检 | 外部输入可控(用户可构造嵌套结构)时必须设置上限 |
| 规模侧约束 | 对单次遍历的元素数与结果集大小设上限 | 与深度约束互补:宽度同样会造成内存问题 |
| 运行时配置 | 调整 -Xss | 抬高阈值而非消除风险;与线程数存在权衡(线程栈总占用 = -Xss × 线程数) |
深度保护的意义在于把失败从"不可控的栈溢出"变为"可观测、可处理的返回错误"。栈溢出发生在调用链深处,异常可能跨越大量业务帧,且无法在业务层优雅降级;显式校验则把失败限制在入口处。
线上已经出现栈溢出时的处理顺序:
- 从异常堆栈中重复出现的方法名确定递归位置,重复段长度反映深度量级;
- 用线程转储确认调用链形态,判读方法见 Java 应用诊断与部署调优 中线程转储的判读一节;
- 区分是终止条件缺陷(深度单调增长、与输入无关)还是数据形状导致(深度与输入规模同阶);
- 前者修正终止条件,后者改为迭代或队列驱动;
-Xss的调整只作为临时缓解; - 增加深度校验与输入侧限制,避免同类数据再次触发。
四、总结
定位。 递归是把自相似问题用同一段逻辑覆盖所有规模的表达方式:只需描述最小规模的处理与由小规模构造大规模的规则,代码量与问题规模无关。它与数学归纳法逐条对应,正确性只需检查终止条件(基础情形)与递归关系(归纳步骤)两端;缺陷也集中在同样的两端。表达力强与运行代价并存,代价集中在调用栈与可能的重复计算上。
三要素。 终止条件、递归关系、状态收缩缺一不可,其中状态收缩最易被忽略,它是"终止条件存在"与"一定会到达终止条件"之间的差别。自顶向下与自底向上是同一递归关系的两种计算方向,前者只用栈帧保存中间结果,后者用显式表,取舍集中在是否只需计算可达状态与是否存在栈深风险。尾递归是递归调用为最后一步的特殊形态,可机械改写为循环;但尾调用优化只在部分语言中成立,JVM 不支持,不能作为跨语言的正确性前提。
调用栈。 每层递归占用一个栈帧(局部变量表、操作数栈、动态链接、返回地址),可承受的最大深度约为 -Xss 除以单层帧大小,通常在数千层量级。深度由数据形状决定:平衡树为 O(log n),退化链为 O(n),因此同一段代码在不同数据上的可处理规模相差数个数量级。深度与递归调用总次数无关,归并排序调用 O(n) 次而栈深只有 O(log n)。栈溢出的四类成因是终止条件缺陷、数据形状退化、单帧体积偏大与 -Xss 偏小;需要与线程创建失败区分,两者的处置方向相反。
递归到迭代。 显式栈模拟(栈中保存待处理的问题)、状态标记法(区分进入与返回两次访问,用于后序)、尾递归改循环是三种改写方式。收益是把空间从线程栈转移到堆、把深度上限从 MB 级提升到 GB 级、把调用开销换成容器操作、并让中途暂停与限流成为可能;代价是中间状态需要显式表达、代码量上升、局部状态的含义需要注释说明。
递归式。 递归树逐层求和最通用;主定理在三种情形下给出快捷结论,判断顺序是先算临界指数 n^(log_b a)、再与 f(n) 比较,落在空隙或规模不成等比时退回展开与代入。二分、归并、快排、树遍历、减治、Karatsuba、Strassen 的结论都可由此直接得到。结论必须标注分析对象(最好、最坏、平均)并区分深度与代价两个维度。
分治。 划分、解决、合并三个步骤对应递归式的子问题个数与规模、直接求解的阈值、以及每层代价。适用条件是子问题独立、规模确实缩小、合并代价可控,第三条最易被低估——合并代价与朴素解法同阶时,分治只增加成本。分治与减治的区别在于子问题个数与是否需要合并步骤,这一区别决定了递归式的形态与结论的推导方式。划分的平衡程度决定递归深度,合并代价决定每层开销,快速排序与归并排序是"把线性代价集中在一侧"的两种做法。
记忆化。 重叠子问题使朴素递归的代价从多项式级退化到指数级;缓存子问题的解把代价拉回"子问题个数 × 单个子问题代价"。记忆化与递推互为等价,差别在是否只计算可达状态、是否有栈深风险、是否可用滚动数组压缩空间。记忆化不解决深度问题。
工程落点。 递归在业务代码中集中出现在树形结构、目录遍历、层级关系与解析器上;风险来自深度不由代码控制(数据形状退化、外部输入可控、规模增长)。改写为迭代或队列驱动的判据是深度是否与规模线性相关、是否需要中断与分层、内存峰值由深度还是宽度决定。深度保护应落实到代码内的显式校验、输入侧的层数上限与规模上限三层,使失败从不可控的栈溢出变为可观测的错误返回。
递归与分治的关系是表达方式与求解策略的关系:递归描述了"如何用同一段逻辑覆盖不同规模",分治描述了"如何把问题拆成独立子问题再合并结果"。递归不必是分治(如链表遍历),分治也可以不用递归(如手写栈的快速排序);两者共同的关键约束只有一条——深度与合并代价必须在设计阶段就被量化,而不是等运行时给出结论。