1.3 递归与迭代：两种运功方式

1.3 递归与迭代：两种运功方式

本节摘要：递归把大问题不断缩小成同型子问题，靠调用栈记住"回来后做什么"；迭代靠循环变量在原地推进。本节用可复算的调用计数揭示递归的两大事故——重复子问题与递归过深，给出记忆化与显式栈两种修复手段，并说明两者在表达力上等价、在开销与可读性上各有代价。

自己调用自己，凭什么能停下来

递归代码第一次看都像悖论：函数还没执行完，怎么就敢再调用自己？答案藏在两件事里：每次调用都把问题规模缩小，直到碰到不再递归的"地基情形"；调用栈自动替你记账，每次调用压入一帧（参数、局部变量、返回地址），子调用返回后弹帧续跑。迭代则把这些状态显式放在循环变量里，由你亲自管理推进与终止。

两种写法表达力等价：一切递归都能改成迭代（最坏用显式栈模拟调用栈），反之亦然。选择标准是可读性与代价，而不是能力。树遍历、分治、回溯天然是递归形状——硬改成迭代反而把逻辑埋进栈操作；简单累积改成递归则白白付出函数调用开销。

心法：调用次数与栈深是递归的两本账

评价一段递归，要同时记两本账：

• 总量账：总调用次数决定时间量级；
• 栈深账：同一时刻叠在栈上的最大帧数决定空间量级，也是爆栈与否的生死线。

用计数器把经典的新手递归——朴素斐波那契——的两本账都翻出来：

# 朴素递归斐波那契：数一数总调用次数
calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n                    # 地基情形：不再递归
    return fib(n - 1) + fib(n - 2)  # 两个同型子问题

for n in (10, 20, 30):
    calls = 0
    fib(n)
    print("fib(%d) 总调用次数 = %d" % (n, calls))
# 输出：
# fib(10) 总调用次数 = 177
# fib(20) 总调用次数 = 21891
# fib(30) 总调用次数 = 2692537
​

次数满足 T(n) = T(n-1) + T(n-2) + 1，与斐波那契数列本身同阶增长——每加一层，调用数按约 1.618 倍的黄金比例翻涨。算 fib(30) 只要两百余万次调用尚可忍受，fib(50) 就要两百多亿次，直接从"瞬间"跌到"分钟级再跌到不可用"。这就是重复子问题事故：fib(28) 被完整重算了两遍，fib(27) 三遍，越靠下的值被重算得越多。

修复手段是记忆化：算过的值存进字典，第二次起直接查表。

# 记忆化之后：每个值只算一遍
memo = {}
calls = 0
def fib_memo(n):
    global calls
    calls += 1
    if n < 2:
        return n
    if n in memo:            # 查账：算过就不重算
        return memo[n]
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

calls = 0
print("fib_memo(20) =", fib_memo(20), "，总调用次数 =", calls)
# 输出：fib_memo(20) = 6765 ，总调用次数 = 39
# 其中真正计算 21 次（0 到 20 每个值各一次），其余 18 次是缓存命中
​

从 21891 次降到 39 次，量级从指数级降到线性。记忆化是第六章动态规划的原始形态：用空间换掉重复的子问题计算。

第二本账：栈深与爆栈

总量账管时间，栈深账管生死。汉诺塔是经典教具——把 n 个盘从 A 挪到 C，借助 B：

# 汉诺塔：移动次数与栈深
moves = 0
def hanoi(n, src, mid, dst):
    global moves
    if n == 1:
        moves += 1
        return
    hanoi(n - 1, src, dst, mid)   # 上面 n-1 个盘挪到中转柱
    moves += 1                    # 最大盘直接挪到目标柱
    hanoi(n - 1, mid, src, dst)   # 再把 n-1 个盘从中转柱挪到目标柱

for n in (3, 10, 20):
    moves = 0
    hanoi(n, "A", "B", "C")
    print("n = %d，移动次数 = %d，理论值 2 的 n 次方减 1 = %d" % (n, moves, 2**n - 1))
# 输出：
# n = 3，移动次数 = 7，理论值 2 的 n 次方减 1 = 7
# n = 10，移动次数 = 1023，理论值 2 的 n 次方减 1 = 1023
# n = 20，移动次数 = 1048575，理论值 2 的 n 次方减 1 = 1048575
​

移动次数是 2ⁿ - 1——64 个盘的传说按每秒挪一次来算要挪上数千亿年，指数级的力量可见一斑。但注意它的栈深只有 n（一条左链一路压到底），空间毫无压力。时间爆炸的代码栈可能很浅；反之，时间线性、深度线性的递归也可能爆栈。CPython 默认递归深度限制约为一千层，超出即抛出 RecursionError：

# 爆栈现场：对链表形状的数据做递归（第 2 章会正式讲链表，这里用嵌套列表模拟）
import sys
print("当前递归深度上限 =", sys.getrecursionlimit())
# 输出：当前递归深度上限 = 1000

def sink(lst):
    if not lst:
        return 0
    return 1 + sink(lst[0])       # 每层深入一层嵌套，栈深与嵌套深度同阶

deep = []
cur = deep
for _ in range(1500):             # 造一条 1500 层的嵌套链
    cur.append([])
    cur = cur[0]

try:
    sink(deep)
except RecursionError:
    print("栈深超过上限，RecursionError：递归过深")
# 输出：栈深超过上限，RecursionError：递归过深
​

修复办法有两条路：调高上限只是止痛（栈仍有限，且每帧都占真实内存）；正法是改成迭代，用显式栈或循环变量接管状态：

# 同一任务的迭代版：栈深恒定为常数
def sink_iter(nested):
    depth, cur = 0, nested
    while cur:                    # 循环变量接管"走到哪了"
        depth += 1
        cur = cur[0]
    return depth

print("迭代版深度 =", sink_iter(deep))
# 输出：迭代版深度 = 1500
​

第三章树遍历会给"显式栈模拟递归"的完整范式，第六章回溯法的栈式写法也源于此。

招式清单：写递归前自检三问

1. 地基情形在哪：最小的、不再递归的输入是什么？漏写地基情形，栈会一直压到爆；
2. 规模确实在缩小吗：每次递归都朝着地基走，才保证终止。参数在奇偶之间来回跳的写法可能永不落地；
3. 子问题是否重叠：重叠就得考虑记忆化或自底向上填表（动态规划），否则指数级总量账迟早爆表。

⚠️ 常见坑：递归写在循环里且循环次数多、递归深度又大时，总量账与栈深账会同时恶化；先估量级再动笔。

💡 关键直觉：调用栈是编译器免费送你的隐式栈——它让分治与回溯的代码接近数学定义；一旦它的深度或开销成为问题，就自己开一个栈，把"记账"接管过来。

本节要点回顾

• 递归两本账：总调用次数定时间量级（朴素斐波那契是指数级），最大栈深定空间量级与爆栈风险（汉诺塔栈深仅 n）；
• 重复子问题用记忆化根治，21 个值各算一遍胜过两万余次调用，这是动态规划的前身；
• 递归过深用迭代根治，显式栈可模拟任何递归，深度不再受调用栈限制；
• 写递归前三问：地基情形、规模收缩、子问题重叠，答不上来先别写；
• 递归与迭代表达力等价，选型看问题形状：分治、回溯、树形问题递归更顺；线性累积问题迭代更省。

总纲三章到此功成。下一章进入第一路根基结构：线性结构，先从最朴素也最容易被低估的数组与链表开始。