第3章 递归

从箱中找钥匙开始

先预测：阁楼里有一个上锁的旧行李箱，钥匙可能在箱内某个盒子里；盒子又可能装着更小的盒子。你会把所有盒子列成待办清单逐个检查，还是写下“检查当前盒子；遇到子盒就按同一规则检查它”？

后一种规则体现。递归函数调用自身，但不是把原问题原封不动地重做：每次调用必须接收一个更小、更接近可直接回答状态的问题。原章先用箱中找钥匙建立这个直觉，再拆分基线条件与递归条件，最后解释调用栈如何保存尚未完成的工作。

原章也提醒读者亲手运行代码，并至少用纸笔追踪一次递归。示例里的伪代码用于突出控制流程，不必纠结某种语言的完整语法；本页再给出可运行的Python版本，把“进入一层、暂停一层、从最深处返回”落实为可测试行为。学习目标不是看到函数名重复就说它“是递归”，而是能指出问题如何缩小、为何必然停止、每层状态存在哪里。

递归并不天然比循环“高级”。同一搜索可以维护一个显式盒子清单：取出一个盒子、检查内容、把子盒加入清单。递归则把“下一步检查哪个盒子”和“检查完后回到哪里”交给语言运行时的调用栈。两种方法都在保存待完成状态，只是状态放置位置不同。

递归条件与基线条件

回答“怎样继续”；回答“什么时候停止”。正确递归同时需要二者：

1. 基线条件覆盖最小合法输入，并直接给出结果。
2. 递归条件把问题变成严格更接近基线的同类问题。
3. 每层只假设较小问题会返回，再完成本层剩余工作。

倒计时是最小例子。输入0时直接结束；输入为正数时，先输出当前值，再调用 countdown(number - 1)：

def countdown(number: int) -> None:
    if number == 0:          # 基线条件
        print("done")
        return
 
    print(number)
    countdown(number - 1)   # 递归条件
 
countdown(3)
# 3, 2, 1, done

这里的是非负整数 number。每层把它减1，而且它不能无限次保持非负并继续下降，所以合法输入一定到达0。只写“有一个 if”不等于证明终止；还要证明所有递归路径都朝基线前进。

调用栈：函数还没做完的工作放在哪里

不是递归专属；普通函数调用同样使用它。意味着最后调用的函数最先返回，就像最后放到一摞盘子顶端的盘子最先拿走。

每次函数调用创建。栈帧通常保存参数、以及。实现细节随语言与运行时而异，但“每次调用有独立状态，返回后恢复调用者”是理解本章代码的可靠模型。

下面的问候程序不是递归，却清楚展示栈怎样处理嵌套函数调用：

def bye(name: str) -> None:
    message = f"bye, {name}"
    print(message)
 
def greet2(name: str) -> None:
    message = f"how are you, {name}?"
    print(message)
    bye(name)
 
def greet(name: str) -> None:
    message = f"hello, {name}"
    print(message)
    greet2(name)
    print("getting ready to say bye")
 
greet("Maggie")

greet 调用 greet2 时，前者暂停，但它的 name、message 和“调用之后继续打印”的位置没有消失；它们留在 greet 栈帧中。greet2 再调用 bye，第三帧位于栈顶。bye 返回后，运行时恢复 greet2；随后恢复 greet。

把新帧放到栈顶叫，移除栈顶帧并恢复上一调用叫。在递归函数中，被压入的不是不同函数名，而是同一函数的多次独立调用；每帧参数可以不同。

递归如何使用调用栈

执行 countdown(3) 时，递归调用逐层压栈：参数3的帧等待参数2，参数2等待参数1，参数1等待参数0。参数0命中基线后立即返回；返回时逐层弹栈，顺序正好与压入顺序相反。

决定同时保留多少栈帧。若处理长度为 n 的线性结构，每次只减少一个元素，最大深度通常与 n 同阶；每帧都要保存状态，因此深递归消耗栈空间。

递归让状态隐含在调用栈中，这是它简洁的来源，也是边界风险的来源。树遍历时，运行时自动记住每个父结点还没访问的分支；循环版必须把这些待处理结点显式放进容器。但隐含状态不等于免费状态。

可能由缺少基线条件导致，也可能发生在逻辑正确但输入极深的递归上。不同语言限制不同；Python还设置了递归深度保护，并不会自动把尾递归普遍改写成循环。工程代码必须根据最大输入深度验证，而不是假设运行时会兜底。

用循环或显式栈替代递归

让状态和容量更可见。箱中找钥匙可以把所有待检查盒子压入列表，循环弹出一个盒子；遇到子盒就继续压入。它与递归深度优先搜索的处理次序相近，但不会为每个盒子创建函数调用帧。

from collections.abc import Iterable
 
class Box:
    def __init__(self, items: Iterable[object]) -> None:
        self.items = list(items)
 
class Key:
    pass
 
def find_key(start: Box) -> Key | None:
    pending = [start]
 
    while pending:
        box = pending.pop()
        for item in box.items:
            if isinstance(item, Key):
                return item
            if isinstance(item, Box):
                pending.append(item)
 
    return None

这个版本把“尚未检查的盒子”直接暴露为 pending。若需要暂停、限制深度、记录路径或处理极深输入，显式栈往往更容易控制。若数据天然是树状且深度有严格小上界，递归版本通常更贴近问题定义。循环适合倒计时这类只需更新少量状态的线性过程。

递归正确性的纸笔追踪

原章建议至少用纸笔逐层走一次递归函数。追踪时不要在脑中“一步跳到答案”，而是为每次调用画独立帧：

1. 写下本层输入和基线判断。
2. 写下递归调用前已经完成的动作。
3. 标记本层正在等待哪个返回值。
4. 到达基线后，按后进先出顺序恢复各帧。
5. 写下每层收到结果后还要完成的动作。

对返回值递归，例如 factorial(4)，factorial(4) 必须等待 factorial(3) 才能完成乘法。基线 factorial(0)=1 返回后，结果依次经过1、2、3、4各层。阶乘只是纸笔练习；本章真正要掌握的是每层独立状态和返回顺序，而不是背一个公式。

原章概念回查

递归函数调用自身，并把工作交给更小的同类问题。递归条件决定怎样继续，基线条件决定怎样停止；缺少基线条件会无限递归，而参数不向基线靠近也会产生同样结果。

调用栈遵循后进先出，也就是栈是后进先出。函数调用创建栈帧，栈帧保存局部变量与返回位置。嵌套调用和递归调用逐层压栈；最深层返回后，返回时逐层弹栈。

递归让状态隐含在调用栈中，所以代码能贴近树和嵌套结构；深递归消耗栈空间，所以逻辑正确也可能栈溢出。循环或显式栈可以替代递归，它们把原本由运行时保存的状态改为程序显式维护。

本章回顾

1. 递归用同一规则处理规模更小的同类问题。
2. 基线条件直接返回，终止继续调用。
3. 递归条件必须让进度度量严格靠近基线。
4. 只有基线而不可达，仍会无限递归。
5. 调用栈按后进先出管理活动函数。
6. 每次调用创建独立栈帧。
7. 栈帧保存参数、局部变量和返回位置。
8. 调用时压栈，返回时弹栈并恢复调用者。
9. 递归把未完成状态隐含在调用栈中。
10. 最大递归深度决定同时存在的帧数。
11. 深度过大可能触发栈溢出。
12. 循环与显式栈能替代递归并显式控制状态。

名词解释