递归：函数调用自己

六行解完汉诺塔

汉诺塔的题面是这样：三根柱子 A、B、C，A 柱上从下到上按大小顺序摞着 n 个盘子，大的在下。每次只允许移动一个盘子，且任何时刻大盘都不能压在小盘上面。要求把 n 个盘子整体搬到 C 柱。

n = 64 时，移动步数是 2^{64} - 1，约 1.8 \times 10^{19} 步。把每一步都显式列出来，在数量上就不可能。

下面这段代码只有六行，它给出了完整的移动顺序：

def hanoi(n, a, c, b):
    if n == 0:
        return
    hanoi(n - 1, a, b, c)
    print(f'盘{n}：{a} -> {c}')
    hanoi(n - 1, b, c, a)

取 n = 3，把这段代码跑一遍，输出是：

盘1：A -> C
盘2：A -> B
盘1：C -> B
盘3：A -> C
盘1：B -> A
盘2：B -> C
盘1：A -> C

七步，与 2^3 - 1 = 7 相符。函数体里没有循环，没有列表，也没有别处保存中间状态；它只是调用了自己两次。

一个函数调用自己，居然能把每一步都做完——这一课要把这件事讲清楚，讲清它的代价，以及它在什么地方会崩。

递归的三个要素

「递归」的英文是 recursion，源自拉丁语 recurrere：re- 表示「回」，currere 表示「跑」，字面意思是「往回跑」。

设一个函数的定义里出现了对自身的调用，则称这个函数是递归函数，这种定义方式称为递归定义。

一个能停下来的递归由三件事构成：

基例是三者里唯一不能省的一项。它允许有两条或更多（例如 n = 0 与 n = 1 各一条），前提是覆盖所有会终止的分支。

汉诺塔的递归关系值得单独看一眼。要把 n 个盘子从 A 搬到 C：先把上面 n-1 个搬到 B，再把第 n 个（此时它上面已经空了）搬到 C，最后把 n-1 个从 B 搬到 C。这三步里，前一步与后一步都是同一个问题的更小规模，中间那一步是一次直接移动。

按这个关系数一下步数：设 T(n) 为搬 n 个盘子的步数，则 T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1，且 T(0) = 0。依次代入得 T(n) = 2^n - 1。n = 64 时就是前面那个 1.8 \times 10^{19}。

调用栈里留下了什么

上一课讲过，栈是只在一端进出的结构，最后压进去的最先被取出。函数调用正是用栈实现的：每发生一次调用，解释器就把一张栈帧（stack frame）压到调用栈的栈顶。栈帧里存着这次调用的形参与局部变量，以及一项容易被忽略的内容——这一层返回之后，控制权交回上一层的哪一行。

函数返回时，栈顶那张帧被弹出，控制权交回帧里记下的那一行。

由此得到两条结论：

• 栈里同时存在的帧数，就是当前的递归深度。
• 最后压入的那层最先返回。这与上一课「后进先出」是同一条规则。

汉诺塔的两层调用，栈的变化过程如下：

栈帧里的「返回到哪一行」是理解递归返回路径的关键。同一段代码被调用多次，每次进入时执行到哪、返回后接着执行哪，靠的是每张帧各自记一份，而不是靠某处的一个全局标记。

这条性质也解释了递归的一个代价：每进入一层就多一张帧，帧里的局部变量各存一份。递归深度越大，占用的内存越多。

亲手推一遍两层

把上面的代码加一层缩进打印，栈的进出就变成可见的输出：

def hanoi_trace(n, a, c, b, depth=0):
    pad = '    ' * depth
    print(f'{pad}进入 hanoi({n}, {a} -> {c})')
    if n == 0:
        print(f'{pad}返回：n 为 0，什么都不做')
        return
    hanoi_trace(n - 1, a, b, c, depth + 1)
    print(f'{pad}移动 盘{n}：{a} -> {c}')
    hanoi_trace(n - 1, b, c, a, depth + 1)
    print(f'{pad}返回 hanoi({n}, {a} -> {c})')

hanoi_trace(2, 'A', 'C', 'B')

进入 hanoi(2, A -> C)
    进入 hanoi(1, A -> B)
        进入 hanoi(0, A -> C)
        返回：n 为 0，什么都不做
    移动 盘1：A -> B
        进入 hanoi(0, C -> B)
        返回：n 为 0，什么都不做
    返回 hanoi(1, A -> B)
移动 盘2：A -> C
    进入 hanoi(1, B -> C)
        进入 hanoi(0, B -> A)
        返回：n 为 0，什么都不做
    移动 盘1：B -> C
        进入 hanoi(0, A -> C)
        返回：n 为 0，什么都不做
    返回 hanoi(1, B -> C)
返回 hanoi(2, A -> C)

缩进的格数就是递归深度。挑几行对一下栈里的内容：

这里能看到基例的实际作用：hanoi(0, ...) 什么也不做就返回，它的存在是为了让「n-1 个盘子」这件事在 n = 1 时有个终止处。每一次「进入」后面都必然跟着一次同层的「返回」，两者配对出现，数量相等。

三个函数与循环版

递归不只在移动盘子上用。下面两个函数是同一件事的两种写法：

def fact_rec(n):
    if n <= 1:
        return 1
    return n * fact_rec(n - 1)

def fact_loop(n):
    r = 1
    for i in range(2, n + 1):
        r *= i
    return r

print(fact_rec(10), fact_loop(10))

3628800 3628800

求和也一样，再加上第三种写法：

def sum_rec(xs):
    if not xs:
        return 0
    return xs[0] + sum_rec(xs[1:])

def sum_loop(xs):
    s = 0
    for x in xs:
        s += x
    return s

def sum_stack(xs):
    st = [(0, 0)]
    total = 0
    while st:
        i, acc = st.pop()
        if i == len(xs):
            total = acc
            continue
        st.append((i + 1, acc + xs[i]))
    return total

a = [3, 1, 4, 1, 5, 9, 2, 6]
print(sum_rec(a), sum_loop(a), sum_stack(a))

31 31 31

三个结果一致。三种写法里只有第一种是递归，第三种把「还没处理到哪」与「已经累加到多少」显式地压进了自己维护的栈——它做的是解释器在递归版里替你做的事。

两种写法在代价上并不对等，这一点值得说清：

第三行是这一节最该记住的一条：递归版看起来最短，代价却最高。xs[1:] 每进入一层就复制一次剩余全部元素，n 层加起来是 O(n^2) 次复制。

缺了基例会怎样

把基例删掉，函数里只剩递归关系：

def broken(n):
    return n + broken(n - 1)

print(broken(5))

跑它的现场是这样（中间重复的行省略）：

  File "broken.py", line 2, in broken
    return n + broken(n - 1)
               ~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

报错的名字说明了原因：broken(5) 调用 broken(4)，再调用 broken(3)，n 一路减下去却永远不会停，因为没有任何一条输入能让它不调用自己。栈里堆到解释器允许的上限，解释器就把它掐断。

[Previous line repeated 996 more times] 这一行给出的是层数。加上最外几层，总数正好是解释器允许的上限。

递归深度有上限

这个上限是可以查的：

import sys
print(sys.getrecursionlimit())

1000

本机（Python 3.14.7，free-threading 构建）实测：默认上限 1000，实际能进入的最深层数是 998（本机实测、非通用值，换机器换版本都会变）。它与上面报错里的 996 是同一件事的不同侧面。

上限用 sys.setrecursionlimit() 可以调高。调高之前要看两件事：

• 栈帧要占内存。 深度 10^5 的递归，即使上限允许，帧本身占的空间也相当可观。
• 上限受解释器栈空间限制。 调到远超实际可用的值，程序可能在抛 RecursionError 之前就异常退出，那种崩溃不会给你一行可读的报错。

指数级的递归陷阱

有些递归不只是慢，它会随规模指数级地变慢。斐波那契数列的朴素递归就是一个典型：

calls = 0

def fib_rec(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib_rec(n - 1) + fib_rec(n - 2)

def fib_loop(n):
    x, y = 0, 1
    for _ in range(n):
        x, y = y, x + y
    return x

两个函数都正确，代价差得极远。把调用次数和耗时数出来（计时用第 2 课的 time.perf_counter() 前后相减）：

import time

for n in (20, 25, 30):
    calls = 0
    t0 = time.perf_counter()
    v = fib_rec(n)
    t1 = time.perf_counter()
    print(n, v, calls, f'{t1 - t0:.6f} 秒')

本机跑出来的三行是：

n 每增加 5，调用次数约乘 11。把 n 从 20 加到 30，规模只增加一半，调用次数却从两万涨到两百七十万——这是指数级增长的形状。n = 30 时循环版是 0.0000074 秒，递归版是 0.175716 秒，相差约 23 700 倍（本机实测、非通用值）。

按这个倍率往下估：n = 45 时递归版约需 0.175716 \times 11^3 \approx 234 秒，n = 50 时约 43 分钟。这道题在 n = 45 上就已经越过了常见的一秒时限。

为什么会重复这么多次？画出来就清楚了：

虚线画的那几个节点是同一个子问题：fib(2) 在这里被算了三次，fib(1) 被算了三次。每往上一层，重复的次数翻一倍，调用总数就这样涨成指数级。

这道题的正确做法是把它改成循环（上表最后一列），或者把算过的结果记下来（动态规划那一课讲这件事）。这里的重点是判断方法：看到「一个函数调用自己两次或更多次、且两次的输入只差常数」时，先把调用次数估出来——n 取一个能跑的小值数一数，看它随 n 增长的速度是不是指数级。

递归改成循环与栈

任何递归都能改写成循环加显式栈，sum_stack 就是一个例子。改写的一般形状是：

• 递归函数里的参数变成栈里的一项；
• 「调用自己」变成压入一项；
• 「返回」变成弹出并处理，把这一层的结果并进上一层。

这样写出来的版本深度不再受解释器上限约束，代价是代码更长、可读性更低。

这一课用到的判断

• 写递归先写基例。 基例要覆盖所有会终止的输入，不只是最常用的那一个。
• 递归关系必须向基例收敛，每一步都让输入严格变小。
• 每层调用在栈里留下一张帧，帧里存形参与局部变量、以及返回到哪一行；栈里同时存在的帧数就是深度。
• 深度是有上限的。本机默认 1000、实测最深 998；深度随 n 线性增长时要考虑改写。
• 调用有一笔固定开销。第 4 课实测过：空循环 8.5 纳秒、调用一个空函数 22.9 纳秒，两者之差约 14 纳秒就是一次调用的净开销（本次复测 8.39 与 21.83 纳秒，差值 13.44 纳秒，与上一课一致）。递归把调用次数放大，这笔开销也一起放大。
• 一个函数调用自己两次以上时，先估调用次数。 输入只差常数的那种写法很容易变成指数级。

• 《算法导论（第 3 版）》第 4 章 分治策略书 · 递归式的引入；当参考书查
• Python 官方文档 · sys.setrecursionlimit官方文档 · 递归深度上限与解释器栈空间