外观
11 - 递归不是自己调用自己:调用栈、终止条件与问题缩减
前置阅读:05 - 栈与队列的解题模型、A - 算法正确性、测试与基准方法。
后续阅读:13 - 二叉树遍历与层级结构、12 - 回溯算法与剪枝。
摘要
统计一个目录下的文件数时,可以先统计各个子目录,再把结果相加。子目录仍然面对同一个问题,只是范围更小,这正是递归适合表达的结构。
本文先用阶乘说明如何缩减问题、何时停止,以及调用返回后如何继续计算;再用目录遍历说明调用栈和显式栈的区别。最后通过树深示例比较递归与队列,并讨论深度失控时的排障方法。
1. 递归的三个组成部分
递归是函数直接或间接调用自身的过程。要让它算出正确结果,不能只看是否“调用了自己”,还要明确三个部分:
- 问题定义:一次调用接收什么输入,返回什么答案。
- 问题缩减:如何把当前问题交给更小的同类问题处理,再组合它们的答案。
- 终止条件:哪些输入已经足够简单,可以直接返回,不再递归。
下面是需放入 Java 类中的局部方法,用于计算非负整数 n 的阶乘,即从 1 到 n 的整数乘积;约定 0! = 1。
java
static long factorial(int n) {
if (n < 0) throw new IllegalArgumentException("n < 0");
if (n <= 1) return 1;
return n * factorial(n - 1);
}n < 0 是非法输入,代码抛出异常;n <= 1 是直接返回的终止条件;其余情况利用 n! = n × (n - 1)! 缩减问题。对非负输入,n 每次减一,最终会到达 1 或直接从 0 返回,因此调用不会无止境地继续。
以 factorial(3) 为例,调用先进入 factorial(2),再进入 factorial(1)。最内层返回 1 后,外层依次算出 2 × 1 = 2、3 × 2 = 6。递归包含“向下拆分”和“返回后组合”两个阶段。
能终止不代表结果一定能用当前类型表示:此方法返回 long,整数阶乘超出其范围时会发生算术溢出,现有代码没有检测它。递归层数也可能先超过线程栈容量,下一节解释这一限制。
2. 调用栈保存什么
factorial(3) 调用下一层后,还要记住“等结果回来,再乘以 3”。这种未完成工作由调用栈保存:从程序执行的逻辑模型看,每次方法调用都有一个栈帧,保存该次调用的参数、局部状态,以及返回后继续执行的位置。内层先完成并返回,外层再继续,符合栈的后进先出顺序。
递归深度是同时尚未返回的递归调用层数,不是整次计算的调用总数。Java 每个线程使用自己的线程栈;同时等待的调用过多,栈空间不足时可能抛出 StackOverflowError。即使终止条件正确,合法但极深的输入也有这个风险。
尾递归指递归调用之后不再有待完成的计算;若运行时支持尾调用优化,就可能复用当前调用的空间。这里的阶乘还要执行乘法,并不是尾递归。Java 通常不保证尾调用优化,即使改写为尾递归,也不能假设不会栈溢出。
可承受深度没有统一数字。它取决于线程栈大小参数 -Xss、平台、JIT(即时编译)状态、方法参数和局部变量等因素;不能把某次机器上成功递归十万层当成接口保证。这里的“十万层”是说明不能泛化单次结果的举例,不是本文的测量记录。
3. 目录遍历
下面是抽象目录模型的局部代码,未提供 Node 定义,也不直接访问文件系统。约定 isFile() 判断是否为文件,children() 返回目录的直接子节点。正常输入为有限、无环且不共享节点的树;目录的子节点集合非 null,本节与下一节共同使用的输入还要求集合内没有 null 元素,遍历期间结构不变。
空节点贡献 0,文件贡献 1;目录本身不计为文件,它的答案是所有子节点答案之和。空目录没有子节点,循环不执行,返回初始值 0。每次进入子目录都只处理原目录的一部分,因此可以沿用同一个方法。
java
static long countFiles(Node root) {
if (root == null) return 0;
if (root.isFile()) return 1;
long count = 0;
for (Node child : root.children()) {
count += countFiles(child);
}
return count;
}若实际遍历会跟随符号链接,或输入包含循环引用,就不能直接套用树的前提:沿某条路径可能再次到达祖先,问题不再严格缩小,递归便可能无法终止。此时需要 visited(已访问集合)记录处理过的节点,重复到达时跳过;节点身份如何判断、链接是否跟随,以及按路径还是按唯一文件计数,都需先定义。以上代码没有实现这些策略。
4. 改为显式栈
目录计数只需累加文件数量,可以把尚未访问的节点放进自己管理的栈。每轮弹出一个节点:若是文件就加一,否则把子节点压栈;栈为空时,所有待处理工作都已完成。下面复用上一节的 Node 和输入前提。
java
static long countFilesIterative(Node root) {
if (root == null) return 0;
java.util.Deque<Node> stack = new java.util.ArrayDeque<>();
stack.push(root);
long count = 0;
while (!stack.isEmpty()) {
Node node = stack.pop();
if (node.isFile()) count++;
else for (Node child : node.children()) stack.push(child);
}
return count;
}在上述树模型下,每个节点都入栈、出栈一次,所以两种写法得到相同的文件数。不过,按原顺序压入子节点会让后面的子节点先被弹出,访问顺序与递归版不同;当前代码只计数,因此不影响结果。ArrayDeque 不允许压入 null,这也是共同输入前提要求子节点非空的原因;递归版单独遇到空子节点时则会返回 0。
显式栈把待处理状态放在堆中的容器里,不再为每个节点增加一层递归调用。它仍需内存,极宽或极深输入也可能耗尽堆空间。若要暂停、恢复、限制深度或记录待处理节点峰值,可以在容器中增加相应状态和检查;当前示例尚未实现这些能力。
在节点操作和累加均按常数成本计算时,两版都访问每个节点一次,时间为 O(n),其中 n 是节点数。递归的调用栈空间随树高增长;显式栈的空间取决于同时待处理的节点数。宽目录一次压入大量子节点,所以改成显式栈并不保证更省内存。
5. 完整可运行示例:递归与队列
下面的完整类对应文件名 RecursionDemo.java,包含 main 入口。本节改为计算二叉树的最大深度:按根到最深叶子路径上的节点数计,空树为 0,单节点树为 1。N 是节点类型,l、r 分别是左右子节点,v 保存值但不参与深度计算。输入仍须是有限、无环且不共享节点的树。
recursive 用递归组合左右子树深度;iterative 使用队列逐层遍历,并不是上一节的显式栈。队列先进先出,适合把同一层节点集中处理。
java
import java.util.*;
/**
* 可运行示例:递归不是自己调用自己:调用栈、终止条件与问题缩减。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class RecursionDemo {
static class N {
int v;
N l, r;
N(int v) {
this.v = v;
}
}
static int recursive(N n) {
// 空节点是最小子问题;非空节点答案来自两个更小子树。
return n == null ? 0 : 1 + Math.max(recursive(n.l), recursive(n.r));
}
static int iterative(N root) {
if (root == null) return 0;
Deque<N> q = new ArrayDeque<>();
q.offer(root);
int d = 0;
while (!q.isEmpty()) {
// 固定本层节点数,循环中新加入的节点留到下一轮。
for (int n = q.size(); n > 0; n--) {
N x = q.poll();
if (x.l != null) q.offer(x.l);
if (x.r != null) q.offer(x.r);
}
d++;
}
return d;
}
// 运行入口:构造一棵三层单支树,比较两种方法的返回值。
public static void main(String[] args) {
N r = new N(1);
r.l = new N(2);
r.l.l = new N(3);
System.out.println(recursive(r));
System.out.println(iterative(r));
}
}调用栈推演与正确性
示例中节点 1 的左子节点是 2,节点 2 的左子节点是 3,所有右子节点均为空。recursive 按下面的过程返回:
| 当前节点 | 左子树深度 | 右子树深度 | 返回值 |
|---|---|---|---|
| 空节点 | 不再递归 | 不再递归 | 0 |
| 3 | 0 | 0 | 1 + max(0, 0) = 1 |
| 2 | 1 | 0 | 1 + max(1, 0) = 2 |
| 1 | 2 | 0 | 1 + max(2, 0) = 3 |
执行时先向下调用,再按表中的非空节点顺序返回;每个父节点必须等左右子树的结果都得到后,才能计算自己的结果。递归把这些等待中的调用保存在线程栈里。
树深公式来自上述定义:经过当前节点的最长路径,必然选择左右子树中更深的一边,再加上当前节点。因此非空树的深度是左右子树最大深度加 1。每次递归都进入严格更小的子树,所以有限无环树在逻辑上一定终止;能否实际完成,还受线程栈等资源限制。
队列版在每轮开始时固定 q.size(),这个数量就是当前层的节点数。内层循环仅处理这些节点,新加入的子节点留到下一轮,因此 d 每轮加一恰好是在统计层数。若随着入队动态读取队列长度,就会混入下一层,无法保持这个边界。
按代码手工推导,main 的预期输出为两行 3,不是实际运行记录。在上述树模型和常数成本假设下,两种方法的时间均为 O(n);递归额外空间为 O(h),其中 h 是树高,队列额外空间为 O(w),其中 w 是最大层宽。单链树考验递归深度,宽树则考验队列容量。
建议用空树、单节点、完全二叉树和极端单链树比较两种方法的结果;空树预期为 0,单节点预期为 1。外部输入的资源限制见下一节。
6. StackOverflowError 排障
遇到 StackOverflowError 时,先保存异常堆栈,再区分“调用无法停止”和“能够停止但层数过深”:
- 同一方法反复出现:递归本来就会产生这种记录,需结合输入和参数变化判断是否在接近终止条件。异常堆栈通常不直接提供参数值,可结合已有日志或调试信息检查。
- 每次都在缩小问题,但输入层数极深:通常是合法输入超过了可承受的递归深度。
- 多个方法循环出现:检查间接递归,例如 A 调用 B,B 又调用 A,确认整个调用循环仍会缩减问题。
- 考虑调整
-Xss时:增大它可以增加单线程栈容量,却不能修复无限递归,还会放大大量线程的虚拟内存需求。具体成本取决于 JVM 与平台,不能只看单线程是否成功。 - 修复后重新检查退化树(形状接近长链的树)、长链和循环引用,分别确认深度预算和防环策略有效。
若协议提供可信的深度信息,可以在进入递归前校验上限;否则应在遍历过程中记录当前深度并及时拒绝超限输入,或改用显式栈。不要先用一个同样不受限的递归去计算深度,否则校验本身就可能栈溢出。显式栈还应记录待处理节点峰值并设置容量预算,避免把线程栈风险转成堆内存风险。
7. 容易踩的坑
- 只写出终止条件,却没有说明每次调用为何一定能到达它。
- 忘记处理空节点,或把递归版允许的空节点直接压入不接受
null的容器。 - 把可能有环或共享节点的图当成树处理,未定义重复访问与计数规则。
- 在每层复制大型集合:多层调用同时持有副本时,内存成本会叠加,不能只计算一份集合的大小。
- 用代码长短判断性能。递归和循环的实际耗时需在相同输入、运行时和测量条件下比较,本文没有做性能测量。
8. 总结
递归的本质是用调用栈保存未完成工作,并把原问题缩减为更小的同类问题。
- 每次递归必须可证明地接近终止条件。
- 深度不可控时应限制输入或使用显式容器,并为容器设置资源预算。
- 树适合按子树递归;图需先定义重复访问与环的处理规则。按层统计的问题可以使用队列。
建议先阅读二叉树遍历与层级结构观察递归在层级结构中的应用,再进入回溯算法与剪枝。