第一次写递归的人，脑子里通常有个挥之不去的念头："我得把每一次调用都想象清楚，才算写对。"
结果越想越乱，最后放弃、改写成循环。
但递归真正的法门恰恰相反——你不必追踪每一次调用的细节，你只需要相信：子问题已经被正确地解决了。
这种"信仰之跃（leap of faith）"是 CS61A 教给你最重要的思维转换之一。本篇从最干净的线性递归，一直讲到会"指数爆炸"的树形递归。

一、递归是什么：函数自己调用自己

是什么：递归（recursion） = 一个函数在自己的定义里调用自己。一个"正确且能停"的递归必须满足三条，CS61A 叫它"递归三定律"：

  1. 有一个或多个基例（base case）：不再自我调用，直接返回；这是递归的"刹车"。
  2. 每次递归都在向基例化简：问题规模严格变小，绝不允许越调越大。
  3. 递归调用解决子问题，再把子问题的结果组合成总结果。

缺了第 1 条 → 无限递归，栈炸；缺了第 2 条 → 永远到不了基例，同样栈炸。两条是递归的命门。

二、线性递归：一条笔直的链

阶乘是最干净的线性递归——每次调用把问题缩小 1：

1
2
3
4
def factorial(n):
    if n == 0:                # 基例：0! = 1
        return 1
    return n * factorial(n - 1)   # 向基例化简，再组合

结合篇一的环境模型，factorial(3) 的"展开—回代"是这样走的：

1
2
3
4
5
6
7
8
展开（向下调用，帧越叠越多）：
factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * (1 * factorial(0)))
= 3 * (2 * (1 * 1))            ← 命中基例，开始回代
回代（向上返回，逐层乘回）：
= 3 * (2 * 1) = 3 * 2 = 6
1
2
3
4
5
调用栈（纵向一条链）：
factorial(3)  ── 等 factorial(2)
  factorial(2)  ── 等 factorial(1)
    factorial(1)  ── 等 factorial(0)
      factorial(0) = 1   ← 基例，栈开始回收

是什么（再确认一遍）：线性递归每一步只产生一个递归调用，调用关系是一条直链，栈深度 = 问题规模 n。

坑：写递归最容易漏基例。比如 factorial 若写成 if n == 1: return 1，那么 factorial(0) 会一路调下去直到栈溢出（RecursionError）。基例必须覆盖所有"最小且合法"的输入，包括边界的 0。

本质一句话：线性递归 = 一次一调用、一条链；基例是刹车，化简是方向盘。

三、斐波那契：树形递归的"优雅陷阱"

把递归写成"多个子调用相加"，就进入了树形递归。fib 是最经典的例子：

1
2
3
4
def fib(n):
    if n == 0 or n == 1:        # 两个基例
        return n
    return fib(n - 1) + fib(n - 2)

逻辑美极了——和数学定义一字不差。但代价藏在调用树里：

1
2
3
4
5
6
7
             fib(5)
            /        \
       fib(4)         fib(3)
       /    \         /    \
   fib(3)  fib(2)  fib(2)  fib(1)
   /  \     /  \    /  \
fib(2) fib(1) ... (fib(2) 被算了两次！)

fib(5) 要算 fib(3) 两次、fib(2) 三次……子问题大量重叠。时间复杂度是恐怖的 O(2ⁿ)——n 每加 1，调用数差不多翻倍。fib(40) 就要上亿次调用，肉眼可见地卡。

坑："代码像数学" ≠ "代码高效"。树形递归在"描述组合/枚举"时极其自然（下节 count_change），但凡涉及"重复子问题"，就必须警惕指数爆炸。

本质一句话：树形递归一个调用分多枝，优雅但易重复计算，复杂度可能是指数级。

四、树形递归的正确打开方式：枚举与组合

树形递归并非原罪——当问题本身就是"每个选择都引出子选择"（组合、路径、决策），它才是最贴合结构的写法。经典题：用硬币 {1,5,10,25} 凑出金额 n，有多少种方式？

1
2
3
4
5
6
7
8
9
10
def count_change(n, coins=(1, 5, 10, 25)):
    if n == 0:
        return 1            # 刚好凑完，算一种
    if n < 0 or not coins:
        return 0            # 凑不出
    use  = count_change(n - coins[0], coins)   # 分支一：用一枚当前硬币
    skip = count_change(n, coins[1:])          # 分支二：换下一种硬币
    return use + skip

print(count_change(10))     # 4 种：10 / 5+5 / 5+1+1+1+1+1 / 1×10

输出：

1
4

每个节点都分出"用 / 不用"两条枝，叶子是基例。这正是树形递归的主场：它把"所有可能性"天然铺成一棵树，你只需描述"每一步怎么分叉"，不用手动管理状态。

坑：树形递归爆栈风险比线性更高。n 稍大就可能 RecursionError。真实工程里这类问题常改用动态规划（DP） 或迭代 + 备忘录，本质就是用空间换掉重复的子树。

五、递归 vs 迭代：不是谁对谁错，是形状匹配

同一问题常有双写法。阶乘的迭代版：

1
2
3
4
5
def factorial_iter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result
维度 递归 迭代
贴合度 自相似结构（树、分治、回溯） 纯线性累加、固定次数循环
可读性 短、直指问题本质 复杂结构写起来绕
空间 有调用栈开销（O(n) 甚至 O(2ⁿ)） 通常 O(1) 几个变量
风险 忘基例/未化简 → 爆栈 循环变量没更新 → 死循环

选型原则：问题本身有"自相似"结构（树遍历、分治、回溯、图搜索）时优先递归，代码量和正确性都更优；纯线性累加、明确次数循环用迭代更直白省内存。

本质一句话：递归贴结构、迭代省内存；按"问题的形状"选工具，而非按习惯。

小结

  • 递归三定律：基例（刹车）+ 向基例化简（方向盘）+ 组合子问题。
  • 线性递归一条链，栈深 O(n)；树形递归多分支，易重复计算 → O(2ⁿ)。
  • 树形递归适合组合/枚举，但警惕指数爆炸与爆栈。
  • 递归 vs 迭代：按问题形状选，不是优劣之分。