1.14 递归那点事儿
沿递归基线、问题缩小、栈帧创建、子结果和回溯合并追踪调用生命周期，用深度边界实验解释栈空间。
学习目标
- 能沿检查基线、缩小输入、压入栈帧、得到子结果和返回合并追踪递归调用
- 能用调用深度、栈帧状态、时间复杂度和空间复杂度解释递归代价
- 能在缺少基线、输入不缩小、共享状态污染和栈深度边界场景中定位首个偏离
1.14 递归那点事儿
本页依据刘欣《码农翻身》（2018 年第 1 版）及出版社公开书目信息，独立重构 1.14 递归那点事儿。正文、代码、图示、实验和练习都是本课程重新设计的教学材料，不复制原书正文、插图、练习答案或代码。
递归不是把循环换成一个神秘的函数调用。一次递归调用需要可达的基线、严格缩小的问题、独立栈帧和可合并的返回值；调用返回时，控制流沿调用链反向回溯。每个栈帧都占用空间，深度边界是实现合同的一部分。
三个会让递归模型失真的陷阱
递归合同
↡本页把故事重构为由可达基线、规模递减、独立栈帧、子结果和回溯合并组成的递归调用模型。不是把函数拟人化，而是要求每次调用都能说明为什么更接近终止、占用什么栈空间、返回什么结果。
对线性递归可以写成：
若每层分支为两个或更多，时间要按调用树分析；空间通常仍由当前调用路径的最大深度决定，除非保留了所有子结果或共享结构。复杂度公式和实际栈轨迹要相互核对。
五个节点到机制证据
检查基线
↡判断当前问题是否已经足够小，可以直接返回结果而不再创建递归调用的阶段。必须覆盖空、单元素、最小数值和错误输入等边界。基线返回值要与递归分支的结果类型兼容。
缩小输入
↡把当前问题转换为更接近基线的子问题，并能用规模函数证明每次递归严格下降的阶段。是终止性的核心。记录旧规模、新规模和变换规则；如果某条分支规模不变或变大，就应在该边停止。
压入栈帧
↡为一次递归调用保存返回地址、参数、局部变量和等待合并的信息，并把调用深度增加一层的阶段。说明每次调用不是免费的。记录帧 ID、输入、局部状态和深度，才能解释栈溢出和回溯顺序。
得到子结果
↡递归调用返回后，把子问题的值、错误或选择结果交给当前栈帧继续处理的阶段。要绑定调用分支和返回状态。多个子调用必须保留顺序或键，不能用一个共享临时变量覆盖历史。
返回合并
↡当前栈帧把子结果与自身局部贡献组合成父调用需要的结果，并弹出栈帧的回溯阶段。连接递归的正向分解和反向回溯。记录合并公式、弹栈顺序、累计结果和撤销动作，避免只看最终答案。
最小可重放实现
function solve(problem):
if is_base(problem):
return base_result(problem)
smaller = reduce(problem)
child = solve(smaller)
return combine(problem, child)
assert solve(fixed_input) == reference_result
assert reset_and_solve(fixed_input) == reference_result这段草图只表达基线、缩小和合并合同，不复制书中叙事或代码。实际复核应保存输入规模、帧 ID、深度、局部变量、子结果、合并记录、最大深度和复位结果。
五步复核递归调用链
1. 固定基线与规模函数
列出空、最小和边界输入，定义可度量的规模函数，证明每条递归路径都向基线下降。先预测基线返回值。
Lab
基线、栈帧与回溯实验
只改变输入规模或基线条件，观察调用深度、子结果和弹栈合并。
输入规模每次减一，到基线后反向合并
n=3 → frame3 → frame2 → frame1 → base → return 1→2→6
判定
通过：深度、弹栈顺序和结果一致
当前场景：基线递归；记录输入规模、帧 ID、深度、子结果、合并顺序、栈预算和复位。
正常、边界与故障证据
| 样本 | 只改变的变量 | 预期判定 | 必存证据 |
|---|---|---|---|
| 正常 | 基线可达、规模递减、合并纯净 | 栈帧按序压入/弹出，结果一致 | 输入规模、帧、深度、子结果、合并 |
| 边界 | 空输入、最小输入、最大深度或分支数量 | 在基线或明确栈边界停止 | 基线、规模、最大深度、空间预算 |
| 故障 | 一次规模不减、帧污染或合并错误 | 首个调用链违约可定位，修复后重放 | 首差、帧 ID、分支、错误、复位 |
故障诊断：从最深处回到首个错误帧
- 核对基线：确认每个合法输入都有可达终止条件，边界返回值与递归返回类型一致。
- 核对规模：比较父问题和每个子问题的规模函数，找第一条不严格下降的分支。
- 核对栈帧：检查帧 ID、参数、局部状态、分支顺序和最大深度，排除共享变量覆盖或栈空间不足。
- 核对回溯：按弹栈顺序比较子结果、合并公式和撤销动作；修复后从空调用栈重放。
术语表
名词解释
本章出现的专业名词，用大白话再讲一遍。
- 1.14 递归那点事儿
由可达基线、规模递减、独立栈帧、子结果和回溯合并组成的递归调用模型。
- 检查基线
判断当前问题是否足够小并直接返回结果的阶段。
- 缩小输入
把问题转换为规模严格下降的子问题的阶段。
- 压入栈帧
为递归调用保存参数、局部变量和返回信息并增加深度的阶段。
- 得到子结果
当前帧接收带有分支身份的递归返回值或错误的阶段。
- 返回合并
当前帧把子结果与自身贡献组合并弹出栈帧的回溯阶段。
练习
练习
问题 1： 递归函数的输入变小了，为什么仍可能栈溢出？
问题 2： 为什么递归深度为 n 不必然表示时间复杂度也是 n？
问题 3： 一个递归搜索返回了正确结果，但另一个分支的路径记录被覆盖，是否可以接受？
本页小结
1.14 递归那点事儿的关键不是把递归当成语法技巧，而是能证明基线可达、问题严格缩小、栈帧独立、子结果可追踪、回溯合并可解释。完成标准是在基线、深度和共享状态故障中定位首个错误帧，修复后从空调用栈重放并验证结果与空间边界一致。