递归

是什么，为什么存在

递归 是一种控制技术，例程执行时会再次进入自身。调用可以是直接的，例如 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。任何加法完成之前，下降过程会创建四个活动调用。随后返回过程按相反顺序求出各个暂停表达式的值。

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

基本情况与递归情况

应针对调用的完整输入域检查基本情况。二分查找通常使用半开区间 [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() 遇到文件时直接返回，遇到目录时则把同一个契约应用于每个子条目。

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

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

追踪递归二分查找

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

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}")

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 的常规递归防护并不安全。

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")

recursive: depth limit reached
iterative: 1201 nodes

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

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

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

陷阱

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

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

递归边没有取得进展

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

重复计算重叠子问题

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

回溯时丢失路径状态

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

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

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

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

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

延伸阅读

• Python 3.14 sys：递归限制——说明运行时防护，以及限制设置过高的风险。
• Python 3.14 内置异常：RecursionError——说明超过最大递归深度时抛出的异常。
• Python 3.14 教程：把列表用作栈——介绍显式栈遍历所需的基础容器操作。
• MIT 6.005：递归——介绍递归分解、基本情况与递归步骤。