# 递归

Source: https://codewiki.com/zh/foundations/recursion/

> - **what**: 递归（recursion）让例程通过调用自身处理规模更小的同类问题，并用基本情况直接返回结果。
> - **trap**: 递归函数在逻辑上可能完全正确，却仍会因输入深度过大或带有对抗性而耗尽调用栈。
> - **fix**: 证明每条递归边都会减小一个良基度量，追踪栈帧并确定边界；无法安全限定深度时，改用显式栈。

## 是什么，为什么存在

递归是一种控制技术，例程执行时会再次进入自身。调用可以是直接的，例如 `walk()` 调用 `walk()`；也可以是间接的，例如两个例程互相调用。关键在于执行过程能沿调用环回到先前的例程。

实用的递归定义至少包含一个基本情况（base case），无需再次递归调用就能得出答案。递归情况（recursive case）把当前问题缩减为一个或多个规模更小的同类问题，再组合它们的答案。两部分缺一不可：基本情况提供终止时的答案，缩减过程则保证程序能够抵达它。

递归之所以存在，是因为有些数据和问题本身就具有递归结构。目录包含若干条目，其中有些条目仍是目录；树由节点与更小的树组成；分治搜索每次选择更小的区间。沿定义编写的代码可以直接呈现正确性证明所用的边界与缩减关系。

这种技术也把程序与归纳法联系起来。要论证递归算法，应先证明它对最小的有效输入成立，再证明当较小调用正确时，当前调用也能正确组合其结果。这种局部论证无需追踪每个具体输入，就能覆盖所有可达的输入规模。

递归并不天然比迭代更简单或更快。一次调用需要占用执行状态，同时存在的调用数上限取决于输入形状，不仅取决于元素数量。递归结构清晰且深度有可靠上界时可用递归；需要更安全地控制深度时，应使用显式工作列表。

语法树访问器、文件系统遍历、图搜索、解析、二分查找、归并排序、快速排序、回溯和带记忆化的动态规划都会用到递归。有些算法会分出多个递归调用，另一些只有一条递归延续路径，可以直接改写为循环。

### 编码前的三个问题

编写自调用之前，先说明单次调用的契约。对于 `total_bytes(entry)`，契约可以是：返回从当前条目能够到达的所有文件字节总数。递归调用在子条目上遵守同一个契约，而不是执行一个描述模糊的相关任务。

应确定完整的终止集合，不能只考虑一个正常路径下的基值。空集合、叶节点、耗尽的区间、无解情况和无效输入可能各自需要不同处理。如果输入域允许环，那么再次遇到已访问对象也是边界条件，尽管它并不是数学意义上的基本情况。

最后，给出一个会在每条递归边上减小的度量。它可以是非负计数、区间宽度、剩余输入长度、树高，或尚未访问节点组成的有限集合。如果函数存在多个分支或可能重访状态，只说「输入看起来变小了」并不能证明终止。

## 工作原理

函数调用自身时，当前调用与调用其他函数一样会暂停。运行时记录足够的信息，以便子调用返回后恢复执行。这些状态构成调用栈（call stack）上的一个栈帧。

从概念上看，栈帧包含本次调用的参数、局部状态和返回位置。实际布局取决于运行时，因此不要让业务逻辑依赖其表示。可移植的事实是：调用方在被调用方结束前始终处于活动状态。

对于 `total_bytes(directory)`，目录对应的栈帧会依次请求各个子条目的总数。文件命中基本情况并返回自身大小。目录栈帧恢复执行、纳入该结果，最终把总和返回给自己的调用方。

### 调用向下，结果向上

假设 `sum_to(3)` 定义为 `3 + sum_to(2)`，并且 `sum_to(0) == 0`。任何加法完成之前，下降过程会创建四个活动调用。随后返回过程按相反顺序求出各个暂停表达式的值。

| 时刻 | 活动调用，最早的在前 | 下一步操作 |
| --- | --- | --- |
| 下降 | `sum_to(3)` | 调用 `sum_to(2)` |
| 下降 | `sum_to(3) → sum_to(2)` | 调用 `sum_to(1)` |
| 下降 | `sum_to(3) → sum_to(2) → sum_to(1)` | 调用 `sum_to(0)` |
| 基本情况 | `sum_to(3) → sum_to(2) → sum_to(1) → sum_to(0)` | 返回 `0` |
| 回退 | `sum_to(3) → sum_to(2)` | 依次返回 `1` 和 `3` |
| 完成 | `sum_to(3)` | 返回 `6` |

调用栈采用后进先出顺序，最新的栈帧最先结束。「栈展开」指的是正常结果返回或异常传播时，执行逐层经过暂停的调用方。它并不表示算法在输入上反向运行。

### 基本情况与递归情况

应针对调用的完整输入域检查基本情况。二分查找通常使用半开区间 `[low, high)`。空区间的条件应写成 `low >= high`，而不只是 `low == high`；如果后续修改让边界意外跨过，前一种写法仍然安全。

递归情况必须维持调用契约。如果目标大于中间值，搜索 `[middle + 1, high)` 就是同一问题的更小实例。搜索 `[middle, high)` 可能永远重复某个单元素区间，因为整数除法可能再次选中同一个中点。

检查顺序应保证基本情况之前不会执行不安全的操作。树遍历器应在读取不存在的子节点之前识别叶节点，区间搜索应在索引中点之前识别空区间。

### 终止性是一项证明义务

常见的终止性证明会使用变式，即取值范围不存在无限下降链的量。若度量是非负整数，需要证明两个事实：

1. 每个有效调用开始时，度量都不小于零。
2. 每个递归调用都会让度量严格减小。

这两个事实排除了无限下降，因此调用最终必然抵达某个边界。函数发起两个递归调用时，必须分别证明两者都在减小。如果某个分支偶尔以未变化的状态重试，这个度量便无法证明终止。

图中可能存在环，因此图遍历不能只依赖结构直觉。可以记录已访问标识，并把度量定义为可达但尚未访问的节点数。应先标记节点，再探索其邻居，以免反向边抢先重新进入当前节点。

### 分开分析时间与空间

分析时间时应计算调用总数，分析栈空间时应计算同时存在的最大调用数。一棵平衡二叉树的遍历可能以 `O(n)` 时间访问 `n` 个节点，同时调用深度只有 `O(log n)`。链状树仍需 `O(n)` 时间，但调用深度会达到 `O(n)`。

递归二分查找每次只在约一半区间上调用一次，因此时间和调用深度都是 `O(log n)`。朴素递归 Fibonacci 对多数输入都会发起两个重叠调用；其深度为线性，但调用总数呈指数增长。只看深度无法描述总工作量。

某些语言或编译器会消除特定尾调用，但 Python 不承诺尾调用消除。即使把 Python 函数改写成以递归调用作为最后一个表达式，无界深度仍不安全。应把配置的递归限制视作防护栏，而不是输入容量目标。

### 阅读栈帧追踪

有用的追踪应区分进入函数、调用子函数、子函数返回和当前函数返回。只记录进入时的参数可以看到下降过程，却看不到中间答案如何组合。只记录最终结果则无法判断结果来自哪个栈帧。

需要紧凑、便于阅读的追踪时，可以按当前深度缩进。还应包含子问题标识和边界状态，例如节点 ID 或区间边界。不要输出整个递归对象，否则反复出现的嵌套表示会淹没真正需要的证据。

检查可疑分支时，按顺序记录四项事实：

1. 当前调用中与契约有关的输入。
2. 是否命中基本情况，以及返回了什么。
3. 每个子调用的输入，以及调用前的终止度量。
4. 子调用结果，以及当前栈帧如何组合该结果。

调试器通过栈帧呈现同类信息。先停在最深的异常调用，再向上寻找第一个提供无效子问题的调用方。异常栈最上方的栈帧往往只是故障显现的位置，不一定是不变量最先被破坏的位置。

### 选择递归还是显式工作列表

两种形式可以实现相同遍历，但提供的控制面不同。递归代码把待处理工作和恢复位置交给语言运行时，迭代代码则把它们表示为应用数据。

| 需求 | 通常更清晰的形式 |
| --- | --- |
| 规模较小、结构深度有界的树 | 递归 |
| 来自外部或可能呈链状的深度 | 显式栈或队列 |
| 暂停、序列化或分发待处理工作 | 显式工作列表 |
| 自然的后序组合 | 递归，或带阶段的显式栈帧 |

显式栈不一定能优化性能。它占用的内存可能与递归遍历相当，尤其是在遍历宽度很大的前沿时。它的主要优势是可以控制表示、限制、调度和失败行为。

如果算法要求广度优先顺序，应使用队列而不是栈。这会改变节点处理顺序，峰值内存通常也会从深度相关存储变成与前沿宽度相关的存储。因此，转换递归同时也是一次遍历顺序决策。

如果递归版本已经正确，转换时应保持它的可观察契约。访问顺序、错误发生时机、重复节点处理方式和部分结果策略都应一致。让迭代版本接管大输入之前，先在小型树上对比两种实现。

只有严格限制接纳深度时，才适合把递归版本保留为小型测试预言机。两种实现如果带着同一组未经检查的假设，就无法提供独立证据。

## 示例

以下示例使用 Python 3.14，并依次展示结构递归、带追踪的分治调用链，以及面对不安全输入深度时的迭代替代方案。

### 递归汇总目录大小

数据明确区分作为叶节点的文件与作为分支的目录。`total_bytes()` 遇到文件时直接返回，遇到目录时则把同一个契约应用于每个子条目。

<!-- quick -->

```python
# file: folder_size.py
def total_bytes(entry):
    if entry["type"] == "file":
        return entry["bytes"]

    return sum(total_bytes(child) for child in entry["children"])


project = {
    "type": "directory",
    "children": [
        {"type": "file", "bytes": 240},
        {
            "type": "directory",
            "children": [
                {"type": "file", "bytes": 760},
                {"type": "file", "bytes": 120},
            ],
        },
    ],
}

print(f"project: {total_bytes(project)} bytes")
```

```text
project: 1120 bytes
```


<!-- /quick -->

证明过程与数据结构一致。文件会直接返回正确总数。假设每个子调用都能返回正确总数，把这些值相加就能得到正确的目录总数。

终止性要求内存中的结构是一棵有限树。真实文件系统可能包含符号链接环、权限失败，以及遍历期间发生变化的条目。生产遍历器必须明确是否跟随链接、如何识别已访问目录，以及错误会怎样影响总数。

### 追踪递归二分查找

这个搜索使用半开边界。输出的深度展示了活动调用的创建过程；每次递归调用都会先缩小区间，先前的栈帧才能返回。

```python
# file: recursive_binary_search.py
def find_order(order_ids, target, low=0, high=None, depth=0):
    if high is None:
        high = len(order_ids)

    print(f"depth={depth}: search [{low}, {high})")
    if low >= high:
        return -1

    middle = (low + high) // 2
    if order_ids[middle] == target:
        return middle
    if order_ids[middle] < target:
        return find_order(order_ids, target, middle + 1, high, depth + 1)
    return find_order(order_ids, target, low, middle, depth + 1)


orders = [104, 117, 203, 258, 311, 409, 550]
position = find_order(orders, 409)
print(f"order 409 is at index {position}")
```

```text
depth=0: search [0, 7)
depth=1: search [4, 7)
order 409 is at index 5
```

第一个栈帧选中索引 `3`，对应值为 `258`，随后搜索 `[4, 7)`。第二个栈帧选中索引 `5` 并返回。由于不再需要组合操作，该值直接穿过第一个栈帧。

区间宽度 `high - low` 就是终止度量。右分支用 `middle + 1` 排除中点，左分支则把 `middle` 作为不包含在内的上界。只要尚未命中基本情况，两条分支都会严格缩小宽度。

在函数开头输出信息可以展示下降过程。在每次递归调用之后输出，则会按相反顺序展示返回过程。生产代码只有在追踪状态属于 API 时才应传递它；其他情况应使用调试器或结构化日志，避免把诊断永久混入算法。

### 用迭代处理深层树

递归函数和迭代函数实现相同的节点计数契约。生成的输入是一条包含 1,201 个节点的链；它是一棵有效树，但其深度对 Python 的常规递归防护并不安全。

```python
# file: walk_deep_tree.py
def count_nodes_recursive(node):
    return 1 + sum(count_nodes_recursive(child) for child in node["children"])


def count_nodes_iterative(root):
    count = 0
    pending = [root]
    while pending:
        node = pending.pop()
        count += 1
        pending.extend(node["children"])
    return count


root = {"children": []}
for _ in range(1_200):
    root = {"children": [root]}

try:
    print(f"recursive: {count_nodes_recursive(root)} nodes")
except RecursionError:
    print("recursive: depth limit reached")

print(f"iterative: {count_nodes_iterative(root)} nodes")
```

```text
recursive: depth limit reached
iterative: 1201 nodes
```

列表 `pending` 是一个显式后进先出栈。与解释器调用栈不同，应用代码可以检查它、限制其大小、把工作转存到其他位置，或为每个待处理项附加元数据。它占用的空间仍是一项资源成本；迭代只是把这项成本的控制权交给算法，并没有让成本消失。

这种转换较为直接，因为递归函数访问子节点后只需执行加法。如果后序工作很重要，应为每个节点保存显式阶段，例如 `(node, expanded)`，并压入一个在所有子节点之后执行的条目。对于回溯，显式条目还可以携带部分路径或撤销信息。

不要把提高递归限制当作处理外部输入深度的首选修复。更高的设置会允许更多 Python 栈帧，还可能触发更底层的栈故障。显式栈配合应用级限制，能够提供可审查的失败策略。

## 陷阱

### 基本情况没有覆盖完整输入域

> **陷阱:** 代码只处理 `n == 0` 却接受负数 `n`，或者先读取子节点再检查是否为叶节点。名义上的基本情况虽然存在，某些有效或已经接纳的输入却无法安全抵达它。

**修复方法：** 先定义可接受的输入域和每种边界结果，再编写递归情况。在公开边界拒绝无效输入，并把基本检查放在索引或读取子节点之前。测试最小有效值、一个空值和一个无效值。

### 递归边没有取得进展

> **陷阱:** 当 `middle` 可能等于 `low` 时，区间搜索仍递归处理 `[middle, high)`；或者解析器没有消费 token 就重试。相同状态再次出现，调用链会持续增长，直到运行时防护将其终止。

**修复方法：** 在每个递归调用旁写出终止度量，并验证它严格减小。半开区间二分查找应从下一个区间中排除已经测试的中点。边界运算最先在单元素和双元素输入上停滞，因此要加入这两类测试。

### 重复计算重叠子问题

> **陷阱:** 直接翻译递推关系可能反复进入相同状态。朴素 Fibonacci 看似忠实于数学定义，却会产生指数级总工作量；递归路径计数可能重复更大的子树。

**修复方法：** 对小型输入画出调用树或统计调用次数，再用完整输入标识状态。通过记忆化缓存纯子问题结果；如果迭代顺序和内存上界更清楚，也可填充动态规划表。隐藏依赖可能变化时，不要缓存结果。

### 回溯时丢失路径状态

> **陷阱:** 生成的搜索代码向同一个共享列表追加选择，却在提前返回时没有移除它。后续分支会继承过期选择，结果因遍历顺序而异。

**修复方法：** 每次修改都必须配对执行有保证的清理，通常可用 `try`/`finally`；如果额外分配可以接受，也可传递复制后的不可变路径。测试一个失败分支后紧跟成功同级分支的情况。结果存储应与当前路径分离。

### 误以为元素数量限定递归深度

> **陷阱:** 包含数千个节点的树在测试中可能平衡，在生产环境中却可能呈链状。带环对象图根本没有有限结构深度。平均形状无法保护调用栈免受对抗性形状影响。

**修复方法：** 根据最坏形状和信任边界推导深度，不能只看总大小。面对图状输入时记录已访问标识，设置应用级深度或工作预算；无法给出安全上界时，改用显式栈。测试中应覆盖链和环。

### 把提高递归限制当作容量规划

> **陷阱:** 提高 Python 的递归限制可以推迟 `RecursionError`，却不能证明终止，也不会减少每个栈帧的内存。限制过高可能把可控异常变成进程故障。

**修复方法：** 把限制视作运行时防护，并让正常输入深度与它保留充足余量。大型或外部结构上的线性深度递归应改为迭代。如果受控内部代码确实需要修改限制，应针对准确环境测量，并在局部操作结束后恢复设置。

<!-- deep -->

## 终止性、正确性与资源边界

三类主要论证回答不同问题。终止性判断每个接纳的调用是否会结束；部分正确性判断结束的调用是否返回正确结果；资源分析则判断算法可能消耗多少调用、栈帧和待处理工作项。

分开进行这些论证可以暴露遗漏。递归函数可能终止却返回错误答案，也可能对每个有限输入都正确，却因为某个接纳输入需要太多栈帧而无法安全运行。

### 证明模板

首先给出精确的单次调用契约。对于二分查找，契约是：给定有序序列和有效半开边界，返回区间内目标的索引；目标不存在时返回 `-1`。边界也是输入的一部分，所以边界不变量属于契约。

选择变式 `V = high - low`。基本条件为假时有 `V > 0`。左分支把区间改为 `[low, middle)`，右分支改为 `[middle + 1, high)`；两个新区间的宽度都严格小于 `V`，并且保持非负。

接着证明部分正确性。空区间不含目标，所以返回 `-1` 正确。中点等于目标时，返回该索引正确。其他情况下，有序关系会排除一半，而归纳假设保证递归结果对于保留的较小区间正确。

最后说明运行边界。每个调用只保留一个子调用，区间宽度至少减半，所以调用总数和最大深度都是 `O(log n)`。最后这个结论不属于终止性证明，它负责量化成本。

### 分支递推关系

对于树遍历器，一个栈帧可能调用每个子节点。如果输入是一棵树，各子树互不相交，因此即使源代码包含递归调用循环，调用总数仍等于节点数。最大调用深度等于树高；只有树呈链状时，它才等于节点数。

朴素 Fibonacci 的两个分支会重叠。`fib(n - 2)` 调用会重复 `fib(n - 1)` 分支中已经包含的工作。运行时间递推式近似为 `T(n) = T(n - 1) + T(n - 2) + O(1)`，因此即使最深调用链只有 `n` 个栈帧，总工作量仍呈指数增长。

记忆化会改变状态图。每个不同的 `n` 只计算一次，后续调用变成缓存查找，从而把总计算量降为线性状态数。递归深度仍然是线性的，所以面对较大的 `n`，自底向上的循环可能更安全。

### 尾调用位置并不是深度边界

如果某个调用的结果不经调用方继续计算就直接成为调用方结果，该调用就处于尾调用位置。支持相关规则的运行时可以利用这种语法性质消除尾调用，但它本身无法说明输入需要多少个逻辑步骤。

Python 会把普通递归调用保留为可供调试的栈帧，并不保证尾调用消除。因此，尾递归倒计时与非尾递归求和一样可能遇到 `RecursionError`。把 `return countdown(n - 1)` 改写为 `while` 循环，才是可靠的常量栈转换。

累加器参数可以把组合工作移到下降阶段，却不会减少 Python 栈帧数量。只有它能让状态转换更清晰时才应使用，不能把它当作栈安全保证。运行空间应根据语言保证和实际实现确认，而不是根据「尾调用」一词推断。

### 环与标识

递归数据定义往往假设输入是树，但应用对象可能形成图。父链接、符号链接、共享依赖或恶意自引用都会破坏「沿边移动必然得到更小结构值」的假设。没有已访问集合时，树高证明不再成立。

环检测应使用稳定的节点标识。先标记标识，再遍历出边；同时决定重复节点应被跳过、报告为环，还是作为共享引用再次计数。这些策略会产生不同的正确答案，因此选择必须写入函数契约。

已访问集合按可达标识数量限制遍历，但自身也占用内存。对于具有 `V` 个可达顶点和 `E` 条已检查边的图，标准遍历耗时 `O(V + E)`，已访问存储为 `O(V)`，此外还需要递归栈或显式工作栈。

### 用显式栈保持顺序

把递归深度优先遍历替换为栈时，可能无意中反转同级节点顺序。递归代码从第一个到最后一个访问子节点。如果可观察访问顺序必须一致，后进先出栈就应按从后到前的顺序压入子节点。

前序遍历会在压入子节点前处理当前节点。后序遍历则需要一个返回阶段，因为递归代码会在所有子调用结束后处理当前节点。可以保存 `(node, next_child_index)` 这样的栈帧，或者先压入 `(node, expanded=False)`，再压入展开后的标记。

这种显式表示与调用栈提供的信息相似，都包含待处理工作、局部进度和恢复位置。其优势在于策略控制：可以限制待处理项、序列化工作、协作式让出执行权，或者返回领域特定的「深度过大」结果，而不依赖解释器故障。

### 异常与清理

异常可能穿过多层递归栈帧。异常传播期间，`finally` 和上下文管理器等语言级清理仍会运行，但子调用之后的普通语句不会运行。因此，依赖后续 `path.pop()` 的回溯代码必须使用有保证的清理机制。

不要在同一个递归例程内部深处捕获 `RecursionError`，然后继续使用已经发生部分修改的状态。该错误表示运行时防护在某个任意的活动栈帧处触发。应在下降前校验深度或设置预算，或者只在能够安全丢弃整个操作的边界捕获它。

<!-- /deep -->

[检查点: foundations/recursion](https://codewiki.com/zh/foundations/recursion/#checkpoint)

## 延伸阅读

- [Python 3.14 `sys`：递归限制](https://docs.python.org/3.14/library/sys.html#sys.getrecursionlimit)——说明运行时防护，以及限制设置过高的风险。
- [Python 3.14 内置异常：`RecursionError`](https://docs.python.org/3.14/library/exceptions.html#RecursionError)——说明超过最大递归深度时抛出的异常。
- [Python 3.14 教程：把列表用作栈](https://docs.python.org/3.14/tutorial/datastructures.html#using-lists-as-stacks)——介绍显式栈遍历所需的基础容器操作。
- [MIT 6.005：递归](https://web.mit.edu/6.005/www/fa16/classes/14-recursion/)——介绍递归分解、基本情况与递归步骤。