Reading 14: 递归（Recursion）

目录 · ← l13 · l15 →

Reading 14: 递归（Recursion）

说明：本讲 sp22 原版使用 TypeScript，本笔记按用户要求提供 Java 代码示例；类型/API 与 sp21（6.031 Java 版）原文保持一致。原文中的 Array<string>、ReadonlyArray<string>、fs.Dir 等 TypeScript/Node 机制已替换为 Java 对应写法（List<String>、Collections.unmodifiableSet、java.io.File）。

概述

本讲讨论「已经拿到规格说明之后，如何实现一个方法」，聚焦其中一个特定技术：递归（recursion）。递归函数由基础情形（base case）与递归步骤（recursive step）两部分定义：基础情形直接算出答案，递归步骤则通过调用自身解决一个更小或更简单的子问题，再组合子问题的结果。递归不是万能工具，但对于「问题本身天然递归」与「数据本身天然递归」的两类情形，它往往是更短、更清晰、更安全、更易修改的分解方式。它对「Safe from bugs」的贡献在于：理想的递归实现中所有变量都是 final、所有数据不可变、所有方法都是纯函数（pure function），因而天然可重入（reentrant）；对「Easy to understand」的贡献在于：递归结构与数学归纳法的证明结构同构，可以直接用「归纳假设成立」的方式推理；对「Ready for change」的贡献在于：可重入的代码可以在并发、回调、相互递归等更多场景下安全使用。代价是栈空间，以及需要警惕的几类典型错误。

核心概念与设计原则详解

递归的定义：基础情形与递归步骤（Base Case & Recursive Step）

定义与目的：基础情形是问题最简单、最小的实例，无法再分解，直接算出结果；递归步骤把一个较大的实例分解成一个或多个更简单的实例，用递归调用解决它们，再组合出原问题的解。它解决的是「如何把一个规格变成实现」的问题，并让实现与数学定义保持同构（易理解）。
直观解释（”它是什么？”）：阶乘有两种定义——乘积形式与递推关系形式。递推形式 0! = 1、n! = n × (n-1)! 直接翻译成代码就是：if (n == 0) return 1; else return n * factorial(n-1);。其中 n == 0 是基础情形，n > 0 是递归步骤。
关键规则与最佳实践：
- 递归实现一定包含基础情形与递归步骤两部分，缺一不可。
- 递归步骤必须把问题实例变换成更小的（或更简单的）实例，否则递归永不终止；若每一步都缩小、基础情形在底部，递归的有限性就有保证。
- 一个递归实现可以有多个基础情形（例如 Fibonacci 的 n == 0 与 n == 1）或多个递归步骤（例如 subsequencesAfter 一次调用自己两次）。
- 基础情形常常对应「空」：空串、空列表、空集合、空树、零。
- 「更小」不一定指数值变小：处理负数时递归到对应的正数（stringValue(-n, base)）也是把问题化简了——递归子问题可以在更微妙的意义上「更简单」。

调用栈（Call Stack）与递归的执行过程

定义与目的：用调用栈图示理解递归的执行：栈随着递归调用不断增长，到达基础情形后开始回卷（unwind），每一层把答案返回给调用者。它服务于「易理解」——递归代码短，但执行过程是动态的，图示能把动态过程变成可检查的对象。
直观解释（”它是什么？”）：执行 factorial(3)：栈依次压入 factorial(3)、factorial(2)、factorial(1)、factorial(0)；factorial(0) 不再递归，直接返回 1；随后 factorial(1) 返回 1、factorial(2) 返回 2、factorial(3) 返回 6。而 Fibonacci 的栈形状不同：它不是「稳定增长到最大深度再收缩」，而是反复地增长又收缩，因为每一步会产生两个递归调用，其中左侧子树完全算完后才轮到右侧。
关键规则与最佳实践：
- 画栈图时要标注每一帧的参数值（如 n = 2），而不只是方法名。
- 追踪「回卷」阶段：返回值是如何被逐层组合的（n * (返回值)）。
- 对 Fibonacci 这类多分支递归，注意同一条子问题会被重复计算多次（fibonacci(3) 会执行基础情形 return 1 共 3 次），这是后面讨论性能与迭代替代的伏笔。
- 递归的可读性来自「相信递归调用会算对」——就像数学归纳法一样，你先假设子问题被正确解决，再关心如何组合。

为问题选择合适的分解（Choosing the Right Decomposition）

定义与目的：同一个规格可以有多种递归分解，好的分解「简单、短、易理解、安全、易于修改」；选错分解会让代码变得别扭而脆弱。
直观解释（”它是什么？”）：subsequences(word) 要求返回单词的所有子序列（保持字母在原词中的顺序）并以逗号分隔，例如 subsequences("abc") 可能返回 "abc,ab,bc,ac,a,b,c,"（注意末尾那个逗号，它前面是空子序列，空子序列也是一个合法子序列）。优雅的分解是：取第一个字母，把所有子序列分成「包含这个字母」与「不包含这个字母」两族，两族合起来恰好覆盖全部子序列。
关键规则与最佳实践：
- 先写出规格，再尝试多种分解，比较哪一种产生的递归步骤最自然。
- 分解应当尽可能是「自我相似」的：子问题与原问题属于同一个规格家族（可直接用已有规格递归）。
- 注意边界与格式细节（如空子序列导致的尾随逗号），它们往往是规格的一部分。
- 如果发现某种分解需要额外的状态或别扭的特判，就考虑换一种分解，或引入辅助方法（下一节）。

辅助方法：用更强的递归假设让分解更简单（Helper Methods）

定义与目的：有时为了让递归分解更简单或更优雅，可以给递归步骤一个更强（或不同）的规格；实现方式是引入一个带额外参数的私有辅助方法。它服务于「易理解」与「易于修改」。
直观解释（”它是什么？”）：subsequences() 的直接递归实现（先把剩余部分的所有子序列算出来，再逐个决定是否加上首字母）需要先 split 再拼接，代码较长。换一种思路：用一个参数 partialSubsequence 记录「已经构造到一半的子序列」，递归调用负责用单词剩下的字母把它补全。以 "orange" 为例：要么把 "o" 选进部分子序列并用 "range" 的所有子序列继续扩展，要么跳过 "o"（部分子序列仍为空串）并用 "range" 继续扩展。
关键规则与最佳实践：
- 辅助方法的规格与原方法不同——它多了一个参数，扮演迭代实现中「局部变量」的角色，在计算过程中保存临时状态。
- 用私有（private）辅助方法实现递归，让公共方法用正确的初值启动它：subsequences(word) 只是 return subsequencesAfter("", word);。
- 不要把辅助方法暴露给客户端。递归分解方式纯粹是实现细节；让客户端去正确初始化 partialSubsequence 会把实现暴露出去，并削弱你未来修改实现的能力。
- Java 中辅助方法应写成 private static，参数用 final 修饰并保持不可变，这样它天然是可重入的。
- 判断是否需要辅助方法的信号：递归步骤需要携带「累积状态」或需要额外的边界参数（如 start/end 区间）。

不要用静态/全局变量保存递归状态（Reentrancy）

定义与目的：递归状态必须放在参数与局部变量里，绝不能放在 static（全局）字段中。这是「可重入代码（reentrant code）」的核心要求：代码可以安全地被重新进入，即在上一次调用尚未完成时再次被调用。
直观解释（”它是什么？”）：Louis Reasoner 不想用辅助方法，于是把 partialSubsequence 写成静态字段。看似省事，实际上：subsequencesLouis("xy") 会产生 7 次递归调用，而 partialSubsequence 是跨所有调用共享的一个变量，每次调用看到的都是「被前面所有调用改过的值」。更糟的是，调用 subsequencesLouis("c") 之后再调用 subsequencesLouis("a")，第二次调用会被第一次调用残留的状态污染——这正是一次「以外部状态为记忆」的经典灾难。
关键规则与最佳实践：
- 可重入代码把状态完全放在参数与局部变量中，不使用 static 变量或全局变量，也不与其他代码或自身的其他调用共享可变对象的别名。
- 递归是「重入」的一种情形（直接递归）；相互递归是另一种。
- 重入性对「安全」有直接价值：重入代码可以安全用于并发、回调（callback）与相互递归等场景。在 Reading 21（并发）中我们会看到，一个方法可能被不同线程同时调用。
- 「把静态字段初始化好再开始递归」并不能解决问题：递归过程中的多次调用仍会互相踩踏。
- 想要「可重入」，就杜绝可变共享状态：final 参数 + 不可变对象 + 纯函数。

选择正确的递归子问题（Choosing the Right Recursive Subproblem）

定义与目的：即使算法方向正确，切分问题的位置也可能决定实现是自然还是别扭。它服务于「易理解」与「代码简洁」。
直观解释（”它是什么？”）：把整数 n 转成某个进制（2 <= base <= 10）的字符串表示，stringValue(16, 10) 应得 "16"，stringValue(16, 2) 应得 "10000"，负数要带负号，且不得有前导零。从最左边（最高位）开始分解看上去符合我们书写的方向，但要先算出位数才能取出最高位；从最右边（最低位）开始则极其自然：n % base 就是最低位，n / base 就是剩下的高位，即 stringValue(n/base, base) + "0123456789".charAt(n%base)。
关键规则与最佳实践：
- 尝试多种切分方向，选择那个能让递归步骤最自然的（这里是「取余 + 整除」）。
- 基础情形要与递归步骤配套：若递归步骤最终会把 n 除到小于 base，那么基础情形就应该是 n < base，返回单个数字字符。
- 注意「分解方向」与「结果拼接顺序」的关系：从低位分解，结果要写成「递归结果的字符串 + 当前位字符」。
- 边界值要显式处理（负数、零、以及整型溢出的极端值——见下文 Java 补充说明）。
- 递归步骤的正确性依赖一个隐含事实：n / base < n（当 n >= 1 且 base >= 2），这正是「问题在缩小」的保证。

递归问题 vs 递归数据（Recursive Problems vs. Recursive Data）

定义与目的：使用递归有两个常见理由：问题是天然递归的（如 Fibonacci、阶乘），或者数据本身是天然递归的（如文件系统、树）。后者几乎必然要求递归实现。
直观解释（”它是什么？”）：文件系统由命名文件组成；有些文件是文件夹，可以包含其他文件。于是文件夹里有文件夹、文件夹里还有文件夹……直到最底层是普通（非文件夹）文件——这就是递归数据。Java 用 java.io.File 表示文件系统：f.getParentFile() 返回父文件夹（也是 File），f.listFiles() 返回它包含的文件数组（File[]），类型自身就是递归的。求一个文件的完整路径名就是天然的递归：fullPathname(f.getParentFile()) + "/" + f.getName()，基础情形是「已在文件系统根部」（getParentFile() == null）。
关键规则与最佳实践：
- 看到递归数据，就用递归实现；用迭代 + 显式栈虽然可能，但代码会复杂得多。
- 基础情形对应数据的「原子」层级（根目录、叶子节点、空树）。
- 注意 Java 补充说明：java.nio.file.Path/Files 提供了更清晰的 API，但数据结构本质依然是递归的。
- 递归遍历往往伴随「累积结果」的需求（打印、收集），这时要特别留意可变别名共享的问题（见下文场景 4）。

相互递归（Mutual Recursion）

定义与目的：如果方法 A 调用方法 B，B 又调用 A，则 A 与 B 互为递归。它常用于处理递归数据，能把两种「粒度」的遍历逻辑分开表达。
直观解释（”它是什么？”）：遍历文件树可以拆成一对方法：visitNode(File file) 负责「处理单个节点」，如果它是目录就调用 visitChildren(file.listFiles())；而 visitChildren(File[] files) 负责「处理一批节点」，对每个文件调用 visitNode(file)。二者递归地互相调用，代码各自都很短。
关键规则与最佳实践：
- 相互递归常常出现在针对递归数据的代码中；Reading 17（Recursive Data Types）会大量使用它。
- 这种写法的一个优势是：客户端可以从「单个起点」（visitNode）或「多个起点」（visitChildren）开始遍历，而不需要任何重复代码。
- 相互递归通常是有意设计的；但意外的相互递归会导致 bug（无限递归、爆栈）。
- 需要跨调用共享的参数（如前缀 pattern）应当作为参数层层传递，而不是放在静态字段里——否则再次破坏可重入性。
- 收集结果的两种风格：调用者传入一个可变的 Set 供写入（模仿迭代风格），或者每个调用返回不可变集合再合并（更安全，见场景 4）。

累积结果的两种风格：可变容器 vs 不可变结果

定义与目的：递归遍历常常需要把结果「收集起来」。可以用一个可变的容器（Set、List）一路传下去并就地修改，也可以让每次递归调用返回新的不可变集合，由调用者合并。后者更安全、更易理解，也更容易并行化。
直观解释（”它是什么？”）：可变风格像一群人共用一块白板，每个人上去添一笔（要小心谁在什么时候擦掉）；不可变风格像每个人各自写一张便条，最后由上层的 addAll 把便条汇总成一份完整清单。
关键规则与最佳实践：
- 采用可变容器时，必须在规格中明确写出「该参数会被修改」（mutating 参数必须在 postcondition 中说明），并且它应当作为参数传递而不是静态字段。
- 采用不可变风格时，每个调用内部用局部 Set<File> resultSet = new HashSet<>(); 累积，向上合并用 resultSet.addAll(visitChildren(...))，返回时用 Collections.unmodifiableSet(resultSet) 防止客户端修改（Java 中对应 sp22 的 ReadonlyArray<string>）。
- 结论（与 Reading 08 一致）：不可变性通常是递归中更安全、更好理解的选择。
- 无论哪种风格，都要保证不会把参数里的可变对象改坏——递归调用之间共享可变别名是最隐蔽的一类错误（场景 2 会展示它的破坏力）。

可重入代码（Reentrant Code）

定义与目的：可重入代码「可以被安全地重新进入」，即在上一次调用尚未完成时再次调用它也是正确的。递归是重入的一个特例。
直观解释（”它是什么？”）：factorial(n-1) 可以在 factorial(n) 还没算完时被调用，是因为每次调用都有自己的参数与局部变量（各自的栈帧）。反之，如果实现依赖某个共享的「当前进度」，重入就会互相干扰。
关键规则与最佳实践：
- 可重入代码把状态完全保存在参数与局部变量中，不使用 static/全局变量，不与其他代码或自身的其他调用共享可变对象别名。
- 直接递归与相互递归都会造成重入；并发程序则会造成「真正的」同时重入。
- 尽量让代码可重入：它更安全，并能在并发、回调、相互递归等更多场景下使用。
- 不可变性是可重入性的天然盟友：不可变参数无需防御性拷贝，也不会被别的递归调用改掉。

递归 vs 迭代：取舍（Recursion vs. Iteration）

定义与目的：两类实现各有代价与收益，选择取决于问题的自然形态与状态管理方式。它同时涉及「易理解」「安全」与资源消耗。
直观解释（”它是什么？”）：阶乘与整数转字符串既可以用 for 循环写，也可以用递归写。迭代版本必然包含可重新赋值的变量（fact = fact * i）或在迭代中被修改的可变对象；要理解程序，你得在脑中想象各个时间点的状态快照。递归版本则可以让所有变量都是 final、所有数据都不可变、所有方法都是纯函数——行为可以仅由「参数 → 返回值」的关系来描述，没有任何副作用。
关键规则与最佳实践：
- 使用递归的三个理由：问题是天然递归的、数据是天然递归的、想更充分地利用不可变性（函数式风格，functional programming）。
- 递归的代价是空间：调用栈会临时占用内存，而栈的大小是有限的。若最大深度与输入规模成对数关系（如递归版二分查找），通常不是问题；若成线性关系（如阶乘、Fibonacci），栈深度就可能成为能处理的最大输入规模的限制。
- 迭代的代价是状态复杂：理解程序需要追踪随时间变化的状态快照。
- 工程上的折中：优先天然递归的分解；对深度线性增长的递归，考虑改写成迭代、引入累积参数（把递归变成尾调用形状）或使用显式栈。
- 关于尾递归（tail recursion）的补充说明（不属于 6.031 原文）：若递归调用是方法体里最后执行的动作（其返回值直接作为本方法的返回值），理论上可以复用当前栈帧，从而把空间降到 O(1)。但 Java 虚拟机并不保证做尾调用优化（JVM 规范允许但不要求），因此 Java 中的尾递归写法通常仍会爆栈；需要真正 O(1) 空间的写法时，应改写为循环，或使用支持尾调用优化的语言特性（如 Scala/Kotlin 的 tailrec，属补充说明）。6.031 的结论因此是：在选择递归前先估计栈深度。

递归与数学归纳法的对应（Recursion and Proof by Induction）

定义与目的：递归实现的结构与数学归纳法的证明结构一一对应，这既解释了「为什么可以相信递归写对了」，也给出了调试与验证的方法。
直观解释（”它是什么？”）：归纳法有「基础情形」与「归纳步骤」；递归实现有 base case 与 recursive step。归纳步骤中我们假设命题对更小的 n 成立（归纳假设），递归步骤中我们假设递归调用会算对、只关心如何组合结果。数据结构方面，二叉树等递归数据结构同样具备「基础情形 + 递归步骤」的结构。
关键规则与最佳实践：
- 写递归时可以分两步推理：先验证基础情形正确（对应归纳基础）；再假设「对所有更小的实例递归调用都返回正确结果」（对应归纳假设），只验证组合逻辑正确。
- 归纳假设的「对更小实例成立」这一前提，正是递归步骤必须缩小问题规模的要求——如果递归步不缩小问题，归纳假设就不适用，而现实中对应的就是无限递归。
- 用归纳法还能帮助你设计测试：为每个基础情形写测试，为每个递归步骤写至少一个「比基础情形大一级」的测试（对应 Reading 03 的测试策略）。
- 归纳法只证明「若终止则正确」，终止性需要单独论证：每一步严格变小 + 基础情形可达。

递归实现的三类常见错误（Common Mistakes）

定义与目的：把调试经验固化成检查清单，能在写代码时就避开大部分递归 bug。
直观解释（”它是什么？”）：三类典型错误是：基础情形完全缺失，或需要多个基础情形但没有全部覆盖（例如 Fibonacci 只写了 n == 0）；递归步骤没有缩小到更小的子问题，导致递归不收敛；以及在递归调用之间无意间共享并修改了指向可变数据结构的别名。
关键规则与最佳实践：
- 写完后先自问：所有基础情形都覆盖了吗？每一步都严格变小了吗？有没有把可变对象作为参数并在递归中修改它？
- 调试递归时优先检查这三条，而不是盯着代码猜。
- 好消息是：迭代实现中的无限循环，在递归实现中通常会变成 StackOverflowError——有 bug 的递归程序有时失败得更快，前提是你不把它 catch 掉（参见 Reading 13 的调试纪律）。
- 「共享可变别名」也是最容易在累积结果模式中犯的错误：把一个 List/Set 一路传下去并在递归中修改，很可能把调用者给的数据改坏。

代码示例与对比分析

场景 1：用静态变量保存递归状态（Louis 的写法）

❌ 错误代码

public class Subsequences {
    // 错误：把“进行中的子序列”放在静态字段里，所有递归调用共享它
    private static String partialSubsequence = "";

    public static String subsequences(String word) {
        partialSubsequence = "";                 // 试图“初始化好再开始递归”
        return subsequencesLouis(word);
    }

    public static String subsequencesLouis(String word) {
        if (word.isEmpty()) {
            // base case
            return partialSubsequence;
        } else {
            // recursive step
            String withoutFirstLetter = subsequencesLouis(word.substring(1));
            partialSubsequence += word.charAt(0);
            String withFirstLetter = subsequencesLouis(word.substring(1));
            return withoutFirstLetter + "," + withFirstLetter;
        }
    }
}

【错误代码的问题】

partialSubsequence 是 static 可变状态，所有递归调用（以及所有线程）共用同一个变量；subsequences("xy") 产生的 7 次 subsequencesLouis 调用看到的都是被前面调用改过的值，结果完全错误。
它不是可重入的：先调用 subsequences("c") 再调用 subsequences("a")，第二次调用会受到第一次残留状态的污染（用户先看到的两个结果 "c" / "c,ca" 就是这样来的）。
把 partialSubsequence 公开并要求客户端「调用前先置空」，等于把实现细节写进规格，客户端的正确性变成了实现正确性的前提——抽象边界被破坏。
即使「在公共方法里先置空」，也不解决问题：递归过程中的多次调用仍会互相覆盖状态。

✅ 正确代码

public class Subsequences {
    /**
     * @param word consisting only of letters A-Z or a-z
     * @return all subsequences of word, separated by commas,
     *         where a subsequence is a string of letters found in word
     *         in the same order that they appear in word.
     */
    public static String subsequences(String word) {
        return subsequencesAfter("", word);
    }

    /**
     * @param partialSubsequence a subsequence-in-progress, consisting only of letters A-Z or a-z
     * @param word consisting only of letters A-Z or a-z
     * @return all subsequences of word, separated by commas,
     *         with partialSubsequence prefixed to each one
     */
    private static String subsequencesAfter(final String partialSubsequence, final String word) {
        if (word.isEmpty()) {
            // base case
            return partialSubsequence;
        } else {
            // recursive step
            return subsequencesAfter(partialSubsequence, word.substring(1))
                 + ","
                 + subsequencesAfter(partialSubsequence + word.charAt(0), word.substring(1));
        }
    }
}

【为什么这样更好】 所有状态都在参数里：每次递归调用都有属于自己的 partialSubsequence 与 word 值（各自的栈帧），因此天然可重入，也不会被其他调用或线程污染。辅助方法是 private 的，客户端只看到原来的规格 subsequences(String)，实现细节被完整地隐藏在抽象边界之后。辅助方法的规格更强——它可以返回「以给定前缀开头的所有子序列」——正是这个更强的（更一般的）假设让递归步骤变得对称而简洁：要么不选首字母，要么选首字母，两条分支各自递归。

【代码对比解说】 两个版本「思路相同」，差别全在状态放哪里。放在静态字段里，状态就成了全局的、跨调用的、不可控的；放在参数里，状态随栈帧自然分层，函数的行为只由输入决定。注意正确版本还顺带修好了一个可重入性问题：它把 partialSubsequence + word.charAt(0) 写成新的字符串（字符串不可变），而不是原地 +=——原地修改会使同一层的两个递归调用互相干扰。另外，公共方法只有一行 return subsequencesAfter("", word);，这正是「用正确的初值启动递归」的标准模式。

【设计原则透视】 这是 Reading 08（Immutability）与 Reading 10（ADT）在本讲的核心落点：可重入性 = 无共享可变状态。static 可变字段在规格上等价于「隐式的、全局的前置/后置条件」，它让方法的规格无法用「参数 → 返回值」描述，从而使推理（和测试）都变得不可靠。辅助方法则展示了「抽象边界」的价值：把更强的规格留给私有辅助方法、把弱而稳定的规格留给公共 API，正是 Reading 06/07 中「规格应该足够强、但不过度暴露实现」的直接应用。Java 里若真有跨调用共享的需求，正确做法是通过参数显式传递（或使用不可变值），而不是依赖 static。

场景 2：递归调用之间共享可变别名并破坏它

❌ 错误代码

/**
 * @param list must be nonempty
 * @return the maximum integer in list
 */
public static int maxList(List<Integer> list) {
    return maxOfRange(list, 0, list.size()-1);
}

// helper method -- finds the max of list[start]...list[end]
private static int maxOfRange(List<Integer> list, int start, int end) {
    if (start == end) {
        return list.remove(start);          // 在递归调用之间破坏了共享的 list
    } else {
        int midpoint = (start + end + 1)/2; // 切分点也错了：区间大小为 2 时右侧会越界
        return Math.max(maxOfRange(list, start, midpoint),
                        maxOfRange(list, midpoint+1, end));
    }
}

【错误代码的问题】

list.remove(start) 在基础情形修改了所有递归调用共享的同一个列表（调用者传入的 list 也被改坏），后续任何一次 list.get(i) 的下标含义都变了，结果不可预测；调用结束后调用者的列表也被清空，属于典型的「破坏参数」。
midpoint = (start + end + 1)/2 配合第二次调用 (midpoint+1, end)，在区间大小恰好为 2 时产生非法的 (end+1, end) 区间，start == end 判断不成立，递归不收敛，最终 StackOverflowError。
这两类错误恰好命中递归「三大常见错误」中的两条：递归步未缩小问题、共享可变别名被破坏性修改。
因为 list 的抽象值在递归过程中不断变化，这个方法的规格「返回 list 中的最大值」变得无法用输入/输出关系描述，测试结果也依赖调用顺序。

✅ 正确代码

/**
 * @param list must be nonempty
 * @return the maximum integer in list
 */
public static int maxList(List<Integer> list) {
    return maxOfRange(list, 0, list.size()-1);
}

/**
 * helper method -- finds the max of list[start]...list[end]
 * @param list must be nonempty and unmodified during the call
 * @param start,end 满足 0 <= start <= end < list.size()
 */
private static int maxOfRange(List<Integer> list, int start, int end) {
    if (start == end) {
        return list.get(start);             // 只观察，不修改
    } else {
        int midpoint = (start + end) / 2;   // 两个子区间都非空且严格更小
        return Math.max(maxOfRange(list, start, midpoint),
                        maxOfRange(list, midpoint + 1, end));
    }
}

【为什么这样更好】 只用 list.get(start) 读取，绝不在递归中修改共享结构，于是「所有递归调用看到的 list 是同一个不可变内容」这一点成为可依赖的前提，方法的抽象值稳定、结果确定，也不会破坏调用者的数据。切分点改为 (start + end) / 2 后，两个子区间 [start, midpoint] 与 [midpoint+1, end] 都严格小于原区间且都非空，因此每一次递归调用都把问题严格缩小，终止性有保证。

【代码对比解说】 这组对比把「共享可变别名」的破坏力暴露得很直观：remove 不仅破坏了列表，还让 start/end 这两个下标失去意义——它们本来描述的是原始列表的位置区间，一旦列表被删掉元素，区间语义就崩了。即使修正了切分点（这是纯粹的算术 bug），共享可变结构的问题依然存在。正确版本体现了一个通用原则：递归参数中出现的可变对象应该被当作只读；如果确实需要在遍历中累积结果，就采用「不可变返回 + 上层合并」的模式（场景 4），或让被修改的容器成为显式文档化的参数。此外注意辅助方法的规格里写明了前置条件 0 <= start <= end < list.size()——即使它是私有方法，写清前置条件也能让「递归步是否合法」变得可检查。

【设计原则透视】 这是 Reading 11（AF/RI）中「抽象值稳定性」的问题：List 的抽象值（元素序列）在递归中被改变了，于是任何依赖「下标 ↔ 元素」对应关系的推理都失效。它也是 Reading 08 的核心警示：别名（aliasing）是可变的代价，当两个引用指向同一个可变对象时，通过一个引用做的修改会从另一个引用「意外地」可见。递归（尤其是分治式递归）天然会产生多个「同时活跃」的引用，因此是可重入性风险最高的场景之一。最后，它说明「三大常见错误」为什么值得背下来当检查清单：本场景同时命中两条，而这类 bug 往往表现为结果错误或爆栈，而不是清晰的异常信息。

场景 3：基础情形不配套、递归方向别扭（整数转字符串）

❌ 错误代码

/**
 * @param n integer to convert to string
 * @param base base for the representation. Requires 2<=base<=10.
 * @return n represented as a string of digits in the specified base, with
 *         a minus sign if n<0. No unnecessary leading zeros are included.
 */
public static String stringValue(int n, int base) {
    if (n < 0) {
        return "-" + stringValue(-n, base);
    } else if (n == 0) {
        return "0";                                  // 基础情形与递归步不配套
    } else {
        return stringValue(n/base, base) + "0123456789".charAt(n%base);
    }
}

【错误代码的问题】

基础情形 n == 0 → "0" 与递归步不配套：递归步把问题降到 n/base，但只有 n 除到 ≤ 9 时才真正需要停下来。结果是 stringValue(16, 10) = stringValue(1, 10) + "6" = ("0" + "1") + "6" = "016"，产生前导零，违反规格。
规格说 2 <= base <= 10，但数字表 "0123456789" 只有 10 个字符；一旦调用者传入 base = 16（超出前置条件），charAt(10) 会抛 StringIndexOutOfBoundsException——错误信息离真正的原因很远。
stringValue(-n, base) 在 n == Integer.MIN_VALUE 时会溢出（-Integer.MIN_VALUE == Integer.MIN_VALUE，仍为负数），于是递归永不缩小，最终 StackOverflowError。补充说明：这是 Java 整型语义特有的边界情形，规格中应当明确 n 的取值范围或显式处理它。
若把递归改成「从最高位开始」的分解，还需要先计算位数，递归步骤会变得复杂且容易错。

✅ 正确代码

/**
 * @param n integer to convert to string
 * @param base base for the representation. Requires 2<=base<=10.
 * @return n represented as a string of digits in the specified base, with
 *         a minus sign if n<0. No unnecessary leading zeros are included.
 */
public static String stringValue(int n, int base) {
    if (n < 0) {
        // 递归子问题在更微妙的意义上更简单：化为正整数
        return "-" + stringValue(-n, base);
    } else if (n < base) {
        // base case：已是一位数字，直接取出；与递归步 n -> n/base 配套
        return "0123456789".substring(n, n + 1);
    } else {
        // recursive step：最低位用 n%base，高位用 n/base（严格变小）
        return stringValue(n / base, base) + "0123456789".charAt(n % base);
    }
}

【为什么这样更好】 基础情形 n < base 与递归步 n / base 严格配套：每次递归都保证 n / base < n（因为 base >= 2 且 n >= base >= 2），因此问题必然收敛到基础情形，且结果天然没有前导零（最高位一定落在基础情形里一次取出）。负数的处理把问题归约到正数，属于「更简单」而非「更小」的化简，同样合法。

【代码对比解说】 错误的版本错在一个非常典型的思路上：「我知道 0 是基础情形」——这对阶乘是对的，但对于「逐位输出」的问题，0 并不是唯一能直接返回的输入，任何 0 <= n < base 都能直接返回一位数字。基础情形的选择必须由递归步的形状反推：递归步每次做 n / base，那么「不能再整除」的状态就是 n < base。另一处对照是分解方向：从最高位开始分解需要先算位数（要么额外循环，要么引入辅助方法），而从最低位开始只需 % 与 /，因此递归步变成一行、拼接顺序也自然（先递归结果、再当前位字符）。

【设计原则透视】 这组对比同时展示了「基础情形与递归步必须配套」和「规格的边界要写清楚」两点。前置条件 2 <= base <= 10 之所以必须写明，正是因为实现只支持 10 个数字字符；若将来要支持 base = 16，正确做法是修改数字表并更新规格（Ready for change），而不是让 charAt 抛出一个含义晦涩的异常。另一个与 Reading 06/07 有关的点：规格里写「No unnecessary leading zeros」不是可有可无的修辞——它是一条可测试的后置条件，恰好就是两个版本的区别所在（"016" vs "16"）。最后，Integer.MIN_VALUE 提醒我们：递归的终止性论证依赖「每一步严格变小」，而算术溢出会悄悄破坏这个前提，因此在写递归时也要像 Reading 13 那样对边界值保持警觉。

场景 4：把可变容器一路传下去就地修改（收集遍历结果）

❌ 错误代码

public class FileWalker {
    // 错误一：可变结果容器放在静态字段里，且“顺带”决定了客户端拿到的东西
    private static Set<File> resultSet = new HashSet<>();
    // 错误二：pattern 也放在静态字段里，调用者无法并行/嵌套使用
    private static String pattern = "";

    public static void visitNode(File file) {
        if (file.getName().startsWith(pattern)) {
            resultSet.add(file);
        }
        if (file.isDirectory()) {
            visitChildren(file.listFiles());
        }
    }

    public static void visitChildren(File[] files) {
        for (File file : files) {
            visitNode(file);
        }
    }

    public static Set<File> findMatching(File root, String p) {
        pattern = p;
        // 忘了清空 resultSet：上一次调用的结果会残留，结果集越来越大
        visitNode(root);
        return resultSet;      // 直接把内部可变容器交给客户端：客户端可以随意改坏它
    }
}

【错误代码的问题】

resultSet 与 pattern 都是 static 可变状态，方法不可重入：两次调用互相污染，第二次的结果里混着第一次的残留（忘记清空更是雪上加霜），并发调用会得到完全错误的结果。
返回 resultSet 等于泄露表示（rep exposure）：客户端拿到内部容器后可以随意增删，甚至可以在别的线程里一边遍历一边修改，导致 ConcurrentModificationException 或更隐蔽的错误。
调用者无法从「多个起点」（一批文件）开始遍历而不重复代码，因为遍历状态藏在全局。
方法的规格无法用「参数 → 返回值」表达（它依赖并修改全局状态），因此难以测试、难以推理。

✅ 正确代码

import java.io.File;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class FileWalker {
    /**
     * 在以 file 为根的子树中，找出名字以 pattern 开头的文件或文件夹。
     * @param file    a file in the filesystem
     * @param pattern 前缀，非 null；空串表示匹配全部
     * @return 所有匹配的文件与文件夹；返回的集合不可修改
     */
    public static Set<File> visitNode(File file, String pattern) {
        Set<File> resultSet = new HashSet<>();
        if (file.getName().startsWith(pattern)) {
            resultSet.add(file);
        }
        if (file.isDirectory()) {
            resultSet.addAll(visitChildren(file.listFiles(), pattern));
        }
        return Collections.unmodifiableSet(resultSet);
    }

    /**
     * 从一批根文件出发做同样的搜索。
     * @param files   一批文件，非 null
     * @param pattern 前缀，非 null
     * @return 所有匹配的文件与文件夹；返回的集合不可修改
     */
    public static Set<File> visitChildren(File[] files, String pattern) {
        Set<File> resultSet = new HashSet<>();
        for (File file : files) {
            resultSet.addAll(visitNode(file, pattern));
        }
        return Collections.unmodifiableSet(resultSet);
    }
}

【为什么这样更好】 状态（结果集与模式）分别成为局部变量与参数，因此两个方法都可重入：可以安全地嵌套调用、并发调用，也可以从单个起点（visitNode）或多个起点（visitChildren）启动遍历而无需重复代码。上层用 resultSet.addAll(...) 合并子结果，符合不可变风格；返回时用 Collections.unmodifiableSet(...) 包一层，防止客户端修改内部集合（对应 sp22 的 ReadonlyArray<string> 语义）。Java 补充说明：更彻底的不可变做法是使用 Set.copyOf(resultSet)，它在 Java 10+ 可用，返回的集合同样是不可修改的快照。

【代码对比解说】 两种写法的差别是「谁持有状态」。可变风格像把所有东西写在一块共用的白板上，任何一次调用的结果都可能被下一次调用看到；不可变风格让每次调用各自准备一张便条，由调用者汇总。注意 Collections.unmodifiableSet 只提供不可修改的视图：它防止客户端改坏内部状态，但若内部集合之后被别的代码改动，视图也会跟着变；因此更严格的写法是返回一个副本（Set.copyOf）或返回前就不再持有该集合的引用。另外，这一版把 pattern 变成了显式参数——这不只是「更干净」：它让「在哪棵树、用什么前缀搜索」成为完全由输入决定的事情，从而让方法可以委托、可以递归、可以测试，也让将来的改动（比如加上「忽略大小写」选项）只影响参数列表而不影响全局状态。

【设计原则透视】 这组对比把 Reading 08（Immutability）、Reading 10（ADT）与 Reading 11（AF/RI）串起来：返回内部可变容器属于典型的表示泄露，它直接破坏 ADT 的抽象边界（客户端可以绕过所有 observer 直接改状态）；同时，把状态放进静态字段使方法失去「纯函数」性质，也就失去了可重入性——而可重入性正是本讲反复强调的递归代码的核心优势，并且会在 Reading 21（并发）与 Reading 20（回调）中再次成为关键。用一个更强的规格（visitChildren 接受一批起点）来简化实现，也正是辅助方法思想的延续。

与其他设计原则的关联

Reading 03（Testing）：递归与数学归纳法的对应直接给出测试策略——为每个基础情形写测试，再为「比基础情形大一级」的递归步骤写测试；StackOverflowError 也提示应加入边界/深度测试。
Reading 06/07（Specifications / Designing Specs）：递归分解的目标是「让规格驱动实现」；辅助方法的存在正说明「更强的规格可以让递归更简单」，而把辅助方法私有化则是维护抽象边界的必然要求。
Reading 08（Immutability）：本讲的核心盟友。理想的递归实现中所有变量为 final、所有数据不可变、所有方法为纯函数；反之，共享可变别名是递归 bug 的头号来源（场景 2、场景 4）。
Reading 09（Avoiding Debugging）：递归的常见错误（缺基础情形、不收敛、共享可变别名）正是「让 bug 尽早暴露」的反面；StackOverflowError 比起死循环是更快的失败，配合 Reading 13 的系统化调试效率更高。
Reading 10（Abstract Data Types）：递归遍历是 ADT observer 的常见实现方式；返回内部可变容器会破坏抽象边界，返回不可变集合则不会。
Reading 11（Abstraction Functions & Rep Invariants）：递归中修改共享可变结构会改变其抽象值，让「下标 ↔ 元素」等基于 AF 的推理失效；写递归时用 RI 检查参数是否被改坏。
Reading 13（Debugging）：递归不收敛通常表现为 StackOverflowError；用切片与断言可以在递归深度增加的过程中定位「哪一层开始出错」。
Reading 17（Recursive Data Types）：本讲预告了递归数据（文件系统、树、语法树）与相互递归，下一部分会系统展开，并说明为什么对递归数据必须以递归方式访问。
Reading 20/21（Callbacks / Concurrency）：可重入性是这两讲的前提——回调可能在原方法未返回时被触发，并发则会让方法真正被同时进入；本讲的「无静态可变状态」是可重入的必要条件。

关键要点

两部分结构：任何递归实现都是「基础情形 + 递归步骤」；基础情形要覆盖所有「最小实例」（可能不止一个），递归步骤必须把问题严格变小或变简单。
状态放参数、辅助方法不暴露：需要累积状态时使用私有辅助方法 + 参数，公共方法用正确初值启动递归；绝不用 static 可变字段保存递归状态，客户的规格也不应因你的分解方式而改变。
分解方向要选对：从低位（n % base、n / base）而不是高位切分，往往能得到最自然的递归步与最简洁的拼接表达式。
优先不可变与纯函数：所有变量 final、结果用不可变集合返回（Collections.unmodifiableSet / Set.copyOf），既安全又天然可重入。
先估栈深度再选递归：深度随输入对数增长（如递归二分）通常安全；线性增长（阶乘、朴素 Fibonacci）要警惕 StackOverflowError，Java 不保证尾调用优化。

常见陷阱与注意事项

基础情形缺失或覆盖不全 → 递归永不触底，抛出 StackOverflowError；典型例子是 Fibonacci 只写 n == 0，或「逐位输出」问题误用 n == 0 作为唯一基础情形（并因此产生前导零）。
递归步骤没有缩小问题 → 递归不收敛（例如切分点算错导致子区间比原区间还大），表现为无限递归或错误结果；迭代写法中这相当于死循环。
在递归之间共享并修改可变别名 → 通过一个引用做的修改对另一个引用可见，导致结果错误、下标语义失效、调用者的数据被破坏；list.remove(start) 是教科书级例子。
用静态/全局变量保存递归状态，或把辅助方法暴露给客户端 → 前者使代码不可重入、多次调用互相污染、并发下结果完全错误（「先初始化再递归」并不能修好它）；后者迫使客户端正确初始化实现细节，破坏抽象边界。正确做法是 private 辅助方法 + 公共方法一行启动。
忽略整型边界与深递归 → -Integer.MIN_VALUE 仍为负数导致递归不收敛；朴素 Fibonacci 的指数级重复计算与线性栈深度会让程序在大输入下爆栈或变得极慢。
混用可变与不可变结果收集风格 → 一边传可变容器一边又试图返回不可变结果，容易出现「返回了内部集合的视图但内部仍在被修改」的隐蔽 bug；固定采用一种清晰风格。

思考题（带答案）

问题 1：对比 subsequences() 的两种实现——直接递归（先算 subsequences(restOfWord) 再逐个加上/不加首字母）与 subsequencesAfter(partialSubsequence, word) 辅助方法版本。它们的规格有什么本质区别？为什么说「辅助方法的规格更强」能让实现更简单？

答案：直接递归版本的规格与原方法完全一致：subsequences(word) 返回 word 的所有子序列。因此递归步骤必须在「子问题的答案」上做二次加工——把 subsequencesOfRest 的字符串结果按逗号 split 开，再对每个子序列分别生成「带首字母」和「不带首字母」两个版本并重新拼接，最后还要处理多余的前导逗号。辅助方法版本的规格是 subsequencesAfter(partialSubsequence, word)：返回「以 partialSubsequence 为前缀的、word 的所有子序列」。这个规格比原规格更强/更一般，因为它对任意前缀都成立（原规格只是前缀为空串的特例）。更强的规格让递归步骤变得对称而简单：每一步只需在两条分支中各选一次——不选首字母（前缀不变）或选首字母（前缀加上首字母），两条分支各自递归到 word.substring(1)；基础情形 word.isEmpty() 直接返回前缀本身。这样就不需要 split、不需要字符串预处理、也不需要额外的前导逗号特判。公共方法 subsequences(word) 退化为一行 return subsequencesAfter("", word);：分解方式是实现细节，不应污染客户端的规格，因此辅助方法必须是 private（在 Java 中还应当是 static，因为它不依赖实例状态——这同时让它天然可重入）。

问题 2：下面的辅助方法为什么既可能给出错误结果、又可能抛出 StackOverflowError？请指出两处不同性质的 bug，并说明如何用「三大常见错误」检查清单发现它们。

private static int maxOfRange(List<Integer> list, int start, int end) {
    if (start == end) { return list.remove(start); }
    int midpoint = (start + end + 1)/2;
    return Math.max(maxOfRange(list, start, midpoint), maxOfRange(list, midpoint+1, end));
}

答案：第一处 bug 是「共享可变别名被破坏性修改」：list.remove(start) 修改了所有递归调用共享的同一个列表（也是调用者传入的对象），此后 start/end 这些下标所描述的位置与原列表不再对应，同时还破坏了 list.size()，让后续 list.get(i) 可能越界或读到错误的元素；调用返回后调用者的列表也被改变了。第二处 bug 是「递归步没有严格缩小问题」：midpoint = (start + end + 1)/2 配合右侧区间 (midpoint+1, end)，当区间大小为 2（例如 start=0, end=1）时得到 (2, 1)，此时 start == end 为假、start > end，于是每次递归都停留在同一个非法区间并持续调用自己，最终 StackOverflowError。用三大常见错误清单检查：①基础情形是否存在且覆盖所有最小实例——存在（start == end），但区间被破坏成 start > end 后就不再可用了；②递归步是否缩小问题——不满足；③是否有共享可变别名被修改——满足（存在破坏性修改）。修复方式：把 list.get(start) 换成读取而非删除，并把切分点改为 (start + end)/2，使 [start, midpoint] 与 [midpoint+1, end] 都严格更小且非空。

问题 3：为什么说理想的递归实现「天然可重入」，而可重入性对并发程序（Reading 21）特别重要？请用 factorial 与 subsequencesLouis 两个例子对比说明，并解释为什么 Java 的尾递归通常仍然会爆栈（补充说明）。

答案：可重入代码的定义是「在上一次调用尚未完成时，可以再次被安全地调用」。factorial(n) 满足这一点：它的全部状态（参数 n、局部变量、返回值）都保存在自己的栈帧里，factorial(n-1) 的递归调用对 factorial(n) 没有任何影响，因此多个线程同时调用 factorial 也互不干扰——行为完全由「输入 → 输出」决定，没有副作用，属于纯函数。subsequencesLouis 则相反：它把进行中的部分子序列放在 static 字段 partialSubsequence 里，这个字段是所有调用、所有线程共享的可变状态；同一次递归中的 7 次调用会依次读到被前面调用修改过的值，两次连续调用之间也会互相污染，因而不可重入、不可并发。在并发场景下，不可重入的代码会直接导致数据竞争（data race）与不可重现的错误结果，所以 Reading 21 强调共享可变状态必须被保护或消除；而「把状态放进参数、保持对象不可变」是最简单的消除手段。补充说明：尾递归（递归调用是方法最后执行的动作，其返回值直接作为本方法返回值）在支持尾调用优化的语言中可以复用栈帧，把空间降到 O(1)；但 Java 虚拟机规范允许而不要求尾调用优化，主流 JVM 实现不做该优化，因此 Java 里写成尾递归形状的方法仍然会随着递归深度增长栈帧并最终抛 StackOverflowError。在 Java 中若需要 O(1) 空间，应改写为迭代循环（或使用显式的栈数据结构），而不是依赖尾递归；6.031 的实用结论是：先估计最大栈深度与输入规模的关系（对数还是线性），再决定用递归还是迭代。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li