递归与调用栈

递归函数调用自己时，调用栈保存尚未完成的工作。每次调用创建一个栈帧，最新的栈帧先执行，返回值再交给下方等待的调用者。等待的栈帧也占用内存，因此递归可能在计算尚不复杂时就因深度过大而失败。

可以把栈帧看成便签。第一张写着 fact(4)，它需要先得到 fact(3)，于是把新便签放到上面。一次只处理最上面一张，下方便签保存未完成的工作。画面中的一张便签对应一个栈帧，等待标记说明该帧还有局部工作未完成。

递归为什么需要调用栈

递归函数需要基本情况和递归情况。基本情况不再递归，直接返回；递归情况对更小的输入调用自己，再使用返回值完成剩余工作。

阶乘的基本情况是 n <= 1，返回 1。其他情况下，fact(n) 调用 fact(n - 1)，把返回值保存为 child，再返回 n * child。

fact(4) 调用 fact(3) 后，原栈帧仍保存 n = 4 和待填的 child = ?。等 fact(3) 返回 6，值填入 child，原调用才能计算 4 * 6。

控制流遵循后进先出：最后压入的调用先返回。每个等待中的栈帧都要占用栈空间。

逐步演示

默认计算 fact(4)。

1. 从 answer = fact(n) 开始，n = 4，调用栈为空。
2. 调用 fact(4)，压入新栈帧，局部状态为 n = 4。
3. 检查 4 <= 1，结果为假，不能从基本情况返回。
4. fact(4) 暂停在 child = fact(3)，等待填入 child。
5. fact(3) 压到顶部并执行，fact(4) 在下方等待。
6. fact(3) 检查 3 <= 1，结果为假，暂停在 child = fact(2)。
7. 压入 fact(2)，检查 2 <= 1，结果为假，暂停在 child = fact(1)。
8. 压入 fact(1)。1 <= 1 为真，基本情况返回 1。
9. 返回值交给 fact(2)，填入 child = 1。
10. fact(2) 返回 2 * 1 = 2。
11. fact(3) 收到 child = 2，返回 3 * 2 = 6。
12. fact(4) 收到 child = 6，返回 4 * 6 = 24。
13. 根调用把结果写入 answer = 24，栈再次为空。

观察方向变化：调用向上压入栈帧，返回值向下交给等待的调用者。fact(2) 必须先完成，fact(4) 才能完成。

再切换到 missingBase 代码版本。移除基本情况后，顶部栈帧不断请求下一个栈帧，没有调用能走到返回。

时间与空间复杂度

按本课的单位成本模型，每帧只做常数次工作：判断、可能的递归调用，以及返回前的乘法。共 n 帧（n >= 1），因此时间和栈空间都是 O(n)。n 很大时，可以改写为循环、使用显式栈，或在了解影响后调整递归上限。

缺少基本情况的版本不再实现阶乘，因为它没有停止规则，只能由运行时的递归上限终止。Python 默认上限约为 1000 层，并非六层；本课使用较小的可见上限，以展示失败过程。

边界情况

• n = 1 直接满足基本情况：压入一帧，返回 1，再弹出。
• 本课正常输入最大为 n = 6，这是画布容纳六帧的限制，并非阶乘的定义限制。
• 缺少基本情况时，负数也不会停止递归。fact_without_base(-2) 会调用 fact_without_base(-3)，接着是 -4，继续下降。
• 返回值只有一个去向：调用者等待的 child 槽位，或根调用对应的全局 answer 槽位。

常见错误

• 以为递归复制整个程序。 它为同一个函数创建新栈帧，每帧有自己的局部变量。
• 忘记调用者在等待。 fact(3) 返回前，fact(4) 无法完成乘法。
• 把基本情况当成可选项。 没有停止条件，栈会增长到运行时终止程序。
• 混淆调用顺序和返回顺序。 调用参数依次是 4, 3, 2, 1，返回值依次是 1, 2, 6, 24。
• 把所有 child 当成同一个变量。 fact(2).child 与 fact(4).child 属于不同栈帧。

本课的简化

画面中的栈帧只显示函数名、参数、局部 child 和返回值。实际 Python 栈帧还包含字节码位置、全局变量引用、闭包引用、异常状态和解释器管理信息。本课先保留两点：每次调用有自己的栈帧，当前只有栈顶帧在执行。