递归与树递归
一、递归只有一个问题要想
- 这一篇对应官方 Lecture 9(Recursion)与 Lecture 10(Tree Recursion),给这些零件装上自我调用的引擎。
初学者写递归,遇到的障碍几乎总是同一处:
「
factorial(n - 1)我还没写出来呢,怎么能用它?」
答案是:你已经写出来了。你现在写的这个 factorial 就是它。这就是 61A 反复强调的信心跃迁(leap of faith)——写递归时唯一要想的事,是「假定子问题已经解决,我怎么把它的结果拼成原问题的答案」。
至于子问题为什么正确,交给数学归纳法去保证,而不要求在写代码时同时展开。
二、递归的三件套
任何一个递归函数都由三块组成:
| 部件 | 作用 | 缺了会怎样 |
|---|---|---|
| 递归基(base case) | 最小可解子问题,直接给答案 | 无限递归 → RecursionError |
| 递归步骤(recursive step) | 缩小规模 + 自我调用 | 永远到不了底 |
| 信心跃迁 | 假定子问题正确,只管拼接 | 写着写着开始手动展开 |
1 | def factorial(n): |
输出:
1 | 120 |
递归基写成 n == 0 or n == 1 是刻意的:
n == 0是数学上的定义(0! = 1);n == 1是省一层调用的优化,一并写上也无妨。
如果只写 n == 0,代码同样正确。但要注意——不要把边界判断放进 else 分支。把边界判断放在函数最前面,是确保它不被遗漏的最直接做法。
三、调用栈:每层递归占一个帧
factorial(5) 展开时,Python 真的把五个帧叠了起来:
flowchart TB
G["<b>Global frame</b><br/>factorial → func factorial(n)"]
F5["<b>f1: factorial(n = 5)</b><br/>等 factorial(4) 回来"]
F4["<b>f2: factorial(n = 4)</b><br/>等 factorial(3) 回来"]
F3["<b>f3: factorial(n = 3)</b>"]
F2["<b>f4: factorial(n = 2)</b>"]
F1["<b>f5: factorial(n = 1)</b><br/>命中递归基 → 返回 1"]
G --> F5 --> F4 --> F3 --> F2 --> F1
F1 -.->|"1 原路返回,逐层乘"| F5
栈深 = 递归深度。深度太大就会撞上限:
1 | import sys |
输出:
1 | 撞到了递归上限 |
Python 默认只给 1000 层。工程上遇到深层递归(例如解析嵌套很深的 JSON),要么改写成迭代,要么调 sys.setrecursionlimit 并同步调大线程栈——若只调大递归上限而不相应调大线程栈,会真的耗尽 C 栈并触发段错误,比普通报错更难排查。
四、树递归:一条路径里多次自我调用
判别方法很简单:return 那一行出现了两次以上自我调用,就是树递归。
最经典的例子是数数字和:
1 | def sum_digits(n): |
输出:
1 | 8 |
2024 → 4 + sum_digits(202) → 4 + 2 + sum_digits(20) → …,每条路径只有一次自我调用,这是「线性递归」,不是树递归。它是树递归的退化形态——只有一根枝。
真正的树递归,是下面这种分岔的。
五、count_partitions:多重边界条件
问题:用不超过 m 的正整数,把 n 拆成若干部分相加,共有几种拆法。
思路只有两条路,且恰好覆盖全部情形、互不重叠:
- 至少用掉一个
m:剩下n - m,可选部分仍然是≤ m; - 完全不用
m:剩下n,可选部分降到≤ m - 1。
1 | def count_partitions(n, m): |
输出:
1 | 5 |
count_partitions(5, 3) = 5,五种拆法是 3+2、3+1+1、2+2+1、2+1+1+1、1+1+1+1+1。
两个边界条件各挡一种死路,缺一不可:
| 条件 | 什么时候触发 | 含义 |
|---|---|---|
n == 0 |
刚好拆完 | 找到一种有效拆法 → 记 1 |
n < 0 |
用了太大的部分,超了 | 这条路走死 → 记 0 |
m == 0 |
可用的最大部分没了,但 n 还没拆完 |
这条路走死 → 记 0 |
最常见的错误,是只写了 n < 0 而漏了 m == 0(或者反过来)。
调用树长这样:
flowchart TB
A["cp(4, 2)"]
A --> B["cp(2, 2)"]
A --> C["cp(4, 1)"]
B --> B1["cp(0, 2) → 1"]
B --> B2["cp(2, 1)"]
B2 --> B21["cp(1, 1)"]
B2 --> B22["cp(2, 0) → 0"]
B21 --> B211["cp(0, 1) → 1"]
B21 --> B212["cp(1, 0) → 0"]
C --> C1["cp(3, 1)"]
C --> C2["cp(4, 0) → 0"]
节点数 = 调用总次数。这棵树的分支是「用 m」和「不用 m」两条,深度由 n 和 m 共同决定——比线性递归复杂得多,也是树递归代价高的根源。
六、重复计算的代价:fib 与记忆化
树递归的另一个标志性问题是重叠子问题:
1 | def fib(n): |
输出:
1 | 55 |
fib(10) 里,fib(8) 被算了两次,fib(7) 被算了三次……越往下重复越多。数一数:
1 | calls = 0 |
输出:
1 | 55 |
为了算 fib(10) = 55,函数被调用了 177 次。增长速率约等于黄金比 φⁿ ≈ 1.618ⁿ——n 只加 10,次数就翻一百多倍。
修法是把算过的结果存起来,这就是记忆化(memoization):
1 | memo = {} |
输出:
1 | 354224848179261915075 |
从 fib(10) 要 177 次调用,到 fib(100) 只需约 200 次——重叠子问题一旦只算一次,指数级就塌成线性。
七、小结
| 概念 | 一句话 | 证据 |
|---|---|---|
| 信心跃迁 | 假定子问题已对,只管拼接 | n * factorial(n - 1) |
| 递归基 | 摆在函数最前,不进 else |
缺了 → RecursionError |
| 栈深 | 每层递归一个帧 | 默认上限 1000 |
| 树递归判据 | return 里两次自我调用 |
cp(n-m, m) + cp(n, m-1) |
| 多重边界 | n < 0 与 m == 0 都要 |
漏一个即错 |
| 重叠子问题 | 树递归的隐藏代价 | fib(10) 调用 177 次 |
| 记忆化 | 算过就存,指数塌成线性 | fib_memo(100) 立即返回 |
三条能带走的:
- 写递归只做一件事:假定子问题对了,把答案拼回去。 不要在脑子里展开整棵树,那是计算机的活。
- 递归基和边界条件一起查,缺一不可。
count_partitions的n < 0与m == 0是标准范本。 - 看到
return行里两次自我调用,先问一句「有重复子问题吗」。 有,就上记忆化。

