一、起源:自相似问题的统一表达

1.1 自相似结构:同一逻辑覆盖不同规模

有一类问题由自身的同类问题构成:

  • 求 n 个数之和,等于前 n−1 个数之和加上第 n 个数;
  • 求二叉树的高度,等于 1 加上左右子树高度的较大者;
  • 求一个目录的总大小,等于当前目录下文件大小之和,加上各子目录总大小之和;
  • 从 n 个元素中取出第 k 小的元素,可以先用一个枢轴把元素分成两半,再在其中一半里继续找。

这类问题的共同结构是自相似:整体由同类型的、规模更小的部分组成。表达同一件事有两种方式:

表达方式 代码量的增长 正确性的验证方式
为每个规模分别写一段代码 与问题规模成正比,规模不设上限时无法写完 逐段验证,工作量随规模增长
用一段代码同时覆盖所有规模 固定 验证最小规模与"由小规模得到大规模"两步

递归是后者的形式化:函数在自身的定义中调用自身,并在每次调用时收缩规模参数。它把"要处理多少种规模"这件事,压缩为"如何处理最小规模"与"如何由更小规模的结果构造当前结果"两件事。

1.2 递归与数学归纳的对应关系

递归的正确性论证与数学归纳法逐条对应:

数学归纳法 递归代码
基础情形:验证 P(0) 或 P(1) 成立 终止条件:最小规模直接给出结果
归纳假设:假设对所有 k < n,P(k) 成立 递归调用:直接信任子调用返回的结果,不再展开
归纳步骤:由 P(k) 推出 P(n) 递归关系:把子问题的解组合成当前解

这一对应关系带来两点实践结论。

  1. 递归代码正确性只需检查两端。一端是终止条件是否覆盖了所有可达的最小规模,另一端是组合方式是否真的等价于原问题的定义。中间规模不需要逐个验证,这与归纳法不需要逐项验证是同一件事。
  2. 递归的缺陷也大多出现在这两端。终止条件缺失或边界考虑不全,表现为不终止或结果错误;组合方式写错,表现为返回值漏算或多算。二者都会在中等规模上暴露,但根因始终在两端。

归纳假设的"信任"是递归与手工展开的区别所在。代码不需要在同一处覆盖全部规模,因为每一层调用都会重新执行同一段判断逻辑。这也是递归代码通常很短的原因。

1.3 表达力强与运行代价并存

递归在表达上的优势集中在三类问题上:

  • 自相似的结构化数据:树、目录、表达式、嵌套配置。定义的递归性直接映射为代码的递归性,见 二叉树与二叉搜索树。
  • 分而治之的求解过程:把问题划分、分别求解、再合并,代码结构与解题思路一一对应。
  • 回溯与试探:走到死路时回到上一个分叉点,天然需要保存沿途的决策现场。

代价同样明确,且与代码长度不成比例:

代价类型 来源 影响
调用开销 每次调用需压栈、传递参数、返回 常数因子上升,但量级不变
栈空间 每一层现场占用一个栈帧 空间随深度增长;深度受线程栈容量限制
深度上限 线程栈容量远小于堆容量 深度与数据规模同阶时会触发栈溢出
重复计算 相同子问题被反复求解 量级退化,如朴素递归斐波那契为指数级

前两项是常数与空间层面的代价,可以用工程手段缓解;后两项会改变可解范围,属于设计层面必须处理的问题。递归与迭代的选择、递归式与分治的复杂度分析,都是围绕这四项代价展开。从抽象数据类型的角度看,递归与分治是算法层面的组织方式,而数据结构决定了操作集合,"能做什么"与"以什么代价做"两条主线的分工见 抽象数据类型(ADT)。


二、原理

2.1 递归的三要素

2.1.1 终止条件、递归关系与状态收缩

一段可终止且正确的递归,必须同时具备三个要素:

要素 含义 缺失或错误的后果
终止条件 存在若干规模,其解可直接给出而不需要继续递归 不终止,最终以栈溢出结束
递归关系 当前规模的解可由更小规模的解组合而成 结果错误,或子问题与原问题不等价
状态收缩 每次调用后的问题规模严格小于当前规模 不终止;或规模不降导致代价爆炸

三者中,"状态收缩"最容易被忽略。终止条件存在并不保证会到达终止条件:若某条路径上参数不变化或反向变化,递归仍会一直进行。检查方式是列出每次递归调用时各参数的变化量,确认存在一个单调向终止条件推进的量。

function solve(state):
    if isBaseCase(state):            # 终止条件:最小规模直接求解
        return baseResult(state)
    sub = shrink(state)              # 状态收缩:规模严格减小
    return combine(solve(sub))       # 递归关系:由子问题的解构造当前解

终止条件与边界的对应关系。 终止条件的具体形态由数据结构与问题定义决定,常见的边界有三类:

  1. 空结构:null 引用、长度为 0 的数组或集合、空目录、空树。作用于空结构时通常返回单位元(和为 0、高度为 0、大小为 0)。
  2. 单元素结构:叶子节点、长度为 1 的区间、只有一个元素的集合。这类规模往往需要单独处理,因为不能再划分。
  3. 区间型问题的两种口径:闭区间 [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 字节估算,深度上限落在数千层量级。这一估算的用途是比较量级而非给出精确值:局部变量多、参数体积大的方法单帧更大,可递归的深度相应减小;把方法体中的临时变量提前释放或抽成独立方法,都可能改变单帧大小。

三条推论:

  1. 递归深度由数据形状决定,而非由代码决定。同一段树遍历代码,在平衡二叉树上深度为 O(log n)(平衡树把树高限制在对数级,见 平衡树:AVL 与红黑树),在退化的链式结构上深度为 O(n)。同样的实现,可承受的规模相差数个数量级。
  2. 递归深度与递归调用总次数无关。归并排序的递归调用总数为 2n−1 次,但同一时刻栈上的帧数只有 log₂n 层;树遍历的帧数等于当前路径的长度,与树的节点总数无关。空间复杂度由最大深度决定,这一点在 复杂度与算法分析 中有完整讨论。
  3. 深度是设计参数。把深度写成与输入规模同阶的表达式(如"递归深度等于链表长度"),等于把可处理的规模上限交给了 -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) 渐近正),判断按以下顺序进行:

  1. 写出三项参数:子问题个数 a、规模缩减因子 b、每次划分与合并的代价 f(n)。
  2. 算临界指数:log_b a 与 n^(log_b a)。这是分治结构"叶子侧"的增长速度。
  3. 比较 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))。
  1. 落入空隙或前提不成立时退回递归树或代入法。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 三个步骤

分治法把问题的求解拆成三步:

  1. 划分(divide):把原问题划分为若干个规模更小、类型相同的子问题。
  2. 解决(conquer):递归求解各子问题;当子问题规模足够小时直接求解,不再继续划分。
  3. 合并(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²),此时划分是否平衡已不改变量级。

由此得到两条设计原则:

  1. 尽量使划分均衡。均衡划分让"每层子问题的总规模"保持与原问题同阶,层数才是 log 量级。随机化枢轴、取中位数作为枢轴、按重心分解树,都是把划分推向均衡的手段。
  2. 把工作放在划分阶段而不是合并阶段,或反之。快速排序把代价集中在划分(原地划分 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²)。分治的做法:

  1. 划分:按 x 坐标排序后取中线,把点集分为左右两半;
  2. 解决:递归求左右两半内部的最近点对距离,取较小者 d;
  3. 合并:只需检查跨越中线的点对,且只需检查横坐标距中线不超过 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 深度不确定时的风险

三类风险的共同点是深度不由代码决定:

  1. 数据形状退化。同一段树遍历代码,遇到退化链表形结构时深度等于节点数。这类数据往往来自历史遗留、批量导入或异常写入,测试环境难以覆盖。
  2. 外部输入可控。解析外部数据时,嵌套深度由输入决定。嵌套 JSON、超长表达式、深层 XML 都可以构造出足以触发栈溢出的深度,这类问题同时也是可用性风险。
  3. 规模增长。当前数据深度只有几层,但随着业务演进可能增长;递归深度与规模线性相关的设计,其可承受上限被 -Xss 固定,无法通过扩大堆解决。

与这三类风险对应的处理不是"把 -Xss 调大"(它只抬高阈值且挤压线程数),而是在设计阶段就把深度纳入约束:显式限制深度、把可能深的结构改为迭代、或对输入设置嵌套层数上限。

2.8.3 递归改迭代或队列驱动的选择依据

需求 结构 峰值空间的决定因素
深度优先顺序,深度可控 递归 深度 × 栈帧
深度优先顺序,深度不可控 显式栈 深度 × 元素大小(占用堆)
按层或按批处理 队列(广度优先式) 最大宽度 × 元素大小
子结果先就绪再处理父节点(后序) 递归,或显式栈 + 状态标记 深度 × 元素大小

选择的依据有三条:

  1. 顺序语义:深度优先要求"沿一条路径走到底",栈(或递归)与之同构;广度优先要求"先处理近的、再处理远的",队列与之同构。遍历容器的选择依据与两种顺序的对应关系见 栈与队列 与 图的表示与遍历。
  2. 内存峰值由深度还是宽度决定:很深的窄结构用递归或栈,占用随深度增长;很宽但很浅的结构用队列,占用随宽度增长,可能远大于深度。两种结构混合时要按实际数据分布判断哪一侧更大。
  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. 深度不再受限。递归版本的深度等于目录深度,队列版本的循环层数恒为 1,目录深度再大也不影响栈;代价是队列长度可能随目录宽度增长。
  2. 顺序改变。队列给出的是广度优先顺序(按层级),递归给出的是深度优先顺序。若业务依赖"先处理完一个子目录再处理下一个",队列版本需要额外记录层级并按层处理。
  3. 不适用于需要子结果先就绪的汇总。计算每个目录的总大小要求子目录先计算完成,广度优先无法保证这一点;此时应使用显式栈加状态标记(后序),或拆成两阶段:第一遍收集全部目录,第二遍按深度从深到浅聚合。

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),但只分配一次 避免每层重新分配,需要保证递归调用不交叉使用同一块缓冲区

两点细节值得注意:

  1. 归并的辅助数组应预分配并复用。在每层递归内 new 一个辅助数组会把分配次数提到 O(n) 次,分配量之和仍为 O(n log n) 级别,显著放大 GC 压力。
  2. 原地操作并不总是空间更优。原地划分节省了辅助数组,但快速排序的空间来自递归栈;在划分不平衡时栈深为 O(n),反而超过归并排序的 O(log n) 栈深。空间比较必须把递归栈计入,口径问题见 复杂度与算法分析 中空间复杂度一节。

3.3.3 并行分治的可行性与代价

分治的结构天然适合并行:子问题独立是前提,递归调用可以分配给不同线程。可行性的判断依据是三条:

  1. 子问题相互独立。存在共享可变状态(同一个结果容器、同一块缓冲区)时,要么消除共享(各子问题返回局部结果,最后合并),要么加同步,后者通常抵消收益。
  2. 合并步骤满足结合律或顺序无关。合并运算满足结合律时,各分片的局部结果可以按任意顺序合并;不满足时并行会改变结果,例如依赖元素顺序的"首个满足条件的元素"这类查询无法直接并行。
  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 何时应改用迭代或队列驱动

满足以下任一条时,应把递归改写为显式栈的迭代或队列驱动的处理:

  1. 深度与输入规模线性相关,且规模不受代码控制(链表、退化树、外部输入的嵌套深度)
  2. 已出现或按最坏深度估算会出现的 StackOverflowError
  3. 需要在遍历中途暂停、恢复、分片或限流:帧之间无法保存中间状态,而循环的每一轮都是自然的边界
  4. 需要按层或按批处理:队列天然携带层次信息
  5. 需要控制内存峰值的位置:把占用从线程栈(-Xss,不可扩容)转移到堆(-Xmx,可扩容)
  6. 深度受 -Xss 挤压而无法通过其他手段缓解,且调大 -Xss 会与线程数冲突

反向的判据同样成立:深度可控、逻辑与问题定义同构、且不需要中断时,递归的可读性优势更大,不应为规避一个不存在的深度风险而增加状态机式代码。

3.6.3 深度保护与限流

深度保护的做法分三层,从代码到配置:

层次 做法 要点
代码内显式校验 递归入口检查当前深度,超过上限立即返回错误或降级结果 上限应作为配置项而非魔法数字;错误信息中带上当前深度
输入侧约束 对嵌套类输入设置最大层数,解析外部数据前先做深度预检 外部输入可控(用户可构造嵌套结构)时必须设置上限
规模侧约束 对单次遍历的元素数与结果集大小设上限 与深度约束互补:宽度同样会造成内存问题
运行时配置 调整 -Xss 抬高阈值而非消除风险;与线程数存在权衡(线程栈总占用 = -Xss × 线程数)

深度保护的意义在于把失败从"不可控的栈溢出"变为"可观测、可处理的返回错误"。栈溢出发生在调用链深处,异常可能跨越大量业务帧,且无法在业务层优雅降级;显式校验则把失败限制在入口处。

线上已经出现栈溢出时的处理顺序:

  1. 从异常堆栈中重复出现的方法名确定递归位置,重复段长度反映深度量级;
  2. 用线程转储确认调用链形态,判读方法见 Java 应用诊断与部署调优 中线程转储的判读一节;
  3. 区分是终止条件缺陷(深度单调增长、与输入无关)还是数据形状导致(深度与输入规模同阶);
  4. 前者修正终止条件,后者改为迭代或队列驱动;-Xss 的调整只作为临时缓解;
  5. 增加深度校验与输入侧限制,避免同类数据再次触发。

四、总结

定位。 递归是把自相似问题用同一段逻辑覆盖所有规模的表达方式:只需描述最小规模的处理与由小规模构造大规模的规则,代码量与问题规模无关。它与数学归纳法逐条对应,正确性只需检查终止条件(基础情形)与递归关系(归纳步骤)两端;缺陷也集中在同样的两端。表达力强与运行代价并存,代价集中在调用栈与可能的重复计算上。

三要素。 终止条件、递归关系、状态收缩缺一不可,其中状态收缩最易被忽略,它是"终止条件存在"与"一定会到达终止条件"之间的差别。自顶向下与自底向上是同一递归关系的两种计算方向,前者只用栈帧保存中间结果,后者用显式表,取舍集中在是否只需计算可达状态与是否存在栈深风险。尾递归是递归调用为最后一步的特殊形态,可机械改写为循环;但尾调用优化只在部分语言中成立,JVM 不支持,不能作为跨语言的正确性前提。

调用栈。 每层递归占用一个栈帧(局部变量表、操作数栈、动态链接、返回地址),可承受的最大深度约为 -Xss 除以单层帧大小,通常在数千层量级。深度由数据形状决定:平衡树为 O(log n),退化链为 O(n),因此同一段代码在不同数据上的可处理规模相差数个数量级。深度与递归调用总次数无关,归并排序调用 O(n) 次而栈深只有 O(log n)。栈溢出的四类成因是终止条件缺陷、数据形状退化、单帧体积偏大与 -Xss 偏小;需要与线程创建失败区分,两者的处置方向相反。

递归到迭代。 显式栈模拟(栈中保存待处理的问题)、状态标记法(区分进入与返回两次访问,用于后序)、尾递归改循环是三种改写方式。收益是把空间从线程栈转移到堆、把深度上限从 MB 级提升到 GB 级、把调用开销换成容器操作、并让中途暂停与限流成为可能;代价是中间状态需要显式表达、代码量上升、局部状态的含义需要注释说明。

递归式。 递归树逐层求和最通用;主定理在三种情形下给出快捷结论,判断顺序是先算临界指数 n^(log_b a)、再与 f(n) 比较,落在空隙或规模不成等比时退回展开与代入。二分、归并、快排、树遍历、减治、Karatsuba、Strassen 的结论都可由此直接得到。结论必须标注分析对象(最好、最坏、平均)并区分深度与代价两个维度。

分治。 划分、解决、合并三个步骤对应递归式的子问题个数与规模、直接求解的阈值、以及每层代价。适用条件是子问题独立、规模确实缩小、合并代价可控,第三条最易被低估——合并代价与朴素解法同阶时,分治只增加成本。分治与减治的区别在于子问题个数与是否需要合并步骤,这一区别决定了递归式的形态与结论的推导方式。划分的平衡程度决定递归深度,合并代价决定每层开销,快速排序与归并排序是"把线性代价集中在一侧"的两种做法。

记忆化。 重叠子问题使朴素递归的代价从多项式级退化到指数级;缓存子问题的解把代价拉回"子问题个数 × 单个子问题代价"。记忆化与递推互为等价,差别在是否只计算可达状态、是否有栈深风险、是否可用滚动数组压缩空间。记忆化不解决深度问题。

工程落点。 递归在业务代码中集中出现在树形结构、目录遍历、层级关系与解析器上;风险来自深度不由代码控制(数据形状退化、外部输入可控、规模增长)。改写为迭代或队列驱动的判据是深度是否与规模线性相关、是否需要中断与分层、内存峰值由深度还是宽度决定。深度保护应落实到代码内的显式校验、输入侧的层数上限与规模上限三层,使失败从不可控的栈溢出变为可观测的错误返回。

递归与分治的关系是表达方式与求解策略的关系:递归描述了"如何用同一段逻辑覆盖不同规模",分治描述了"如何把问题拆成独立子问题再合并结果"。递归不必是分治(如链表遍历),分治也可以不用递归(如手写栈的快速排序);两者共同的关键约束只有一条——深度与合并代价必须在设计阶段就被量化,而不是等运行时给出结论。