递归 · Learning Notes

递归把当前问题交给规模更小的同类问题处理，再用基线条件收口。本页说明递归的组成与终止条件，并给出递归加法、汉诺塔和归并三个典型写法。把递归用于“分解—求解—合并”的整体策略见分治法；每次调用在内存中的展开与回退见函数调用与栈帧。

定义

递归是指函数直接或间接调用自身。一个能终止的递归由两部分组成：

基线条件（终止条件）：规模小到可以直接得到答案，不再调用自身。
递归步骤：把当前问题化为一个或多个规模更小的同类问题，调用自身求解，再用返回值组合出当前答案。

两部分缺一不可。只有递归步骤，调用不会停止；只有基线条件，函数处理不了基线以外的输入。

设当前问题的规模为 $n$ 。每次递归调用都让规模严格减小、并最终到达基线条件，是递归能够终止的依据。若某条调用路径上的规模没有变小，程序会一直调用下去，直到耗尽调用栈。

递归的结构

写递归前先回答三个问题

基线是什么？ 最小规模取什么值，答案是什么？
规模如何减小？ 每一步把问题缩小多少，是否一定到达基线？
结果如何组合？ 子问题的返回值怎样合成当前问题的答案？

执行顺序

递归调用不会立刻返回结果：当前调用先暂停，等子调用结束后再继续执行它后面的语句。因此，打印语句写在递归调用之前还是之后，会得到完全不同的输出顺序。汉诺塔的移动顺序就是由三次调用的先后关系决定的。

每次调用都会占用一个栈帧；调用链的展开与回退见函数调用与栈帧。

线性递归与树形递归

线性递归：每次只调用一次自身，调用链是一条线。递归加法属于这一类，规模每步减少1。
树形递归：每次分解成多个子调用，调用过程形成一棵树。汉诺塔每次产生两个规模 $n-1$ 的调用，移动次数满足 $M(n)=2M(n-1)+1$ ， $M(1)=1$ ，解得 $M(n)=2^n-1$ 。

树形递归的调用次数可能随规模指数增长，写之前应先估计调用总量。

例子

递归加法

把列表的和定义为“第一个元素加上其余元素的和”，基线是只剩一个元素。

1
def F(a):
2
    if len(a) == 1:
3
        return a[0]  # 终止条件非常重要
4
    return F(a[1:]) + a[0]
5

6

7
a = [1, 4, 9, 16]
8
print(F(a))

调用F([1, 4, 9, 16]) 时，先递归求出F([4, 9, 16])，返回后再加1，最终得到30。切片a[1:] 会复制剩余元素，所以这份实现除了调用栈之外还会产生 $O(n^2)$ 的复制开销；它适合说明递归结构，不适合作为求和的默认写法。

汉诺塔

Hanoi(n, A, C, B) 表示把 $n$ 个盘子从柱A移到柱C，以柱B作为辅助。移动 $n$ 个盘子可以拆成三步：先把上面 $n-1$ 个移到辅助柱，再把最大的盘子移到目标柱，最后把 $n-1$ 个从辅助柱移到目标柱。

1
count = 1
2

3

4
def main():
5
    n_str = input("请输入盘子个数：")
6
    n = int(n_str)
7
    Hanoi(n, "A", "C", "B")
8

9

10
def Hanoi(n, A, C, B):
11
    global count
12
    if n < 1:
13
        print("False")
14
    elif n == 1:
15
        print("%d:\t%s -> %s" % (count, A, C))
16
        count += 1
17
    elif n > 1:
18
        Hanoi(n - 1, A, B, C)
19
        Hanoi(1, A, C, B)
20
        Hanoi(n - 1, B, C, A)
21

22

23
if __name__ == "__main__":
24
    main()

三次调用的顺序不能交换：第二次调用移动的是最大的盘子，它必须在两次 $n-1$ 规模的搬运之间执行。count记录当前是第几次移动，每输出一次加一； $n$ 个盘子共需 $2^n-1$ 次移动。

归并操作

归并（merge）把两个已经有序的列表合并成一个有序列表。比较两个列表的首元素，取出较小者，再对剩余部分递归归并。

1
def merge(L1, L2):
2
    if len(L1) == 0:
3
        return L2
4
    if len(L2) == 0:
5
        return L1
6
    if L1[0] < L2[0]:
7
        return [L1[0]] + merge(L1[1 : len(L1)], L2)
8
    else:
9
        return [L2[0]] + merge(L1, L2[1 : len(L2)])
10

11

12
X = merge([1, 4, 9], [10])
13
print(X)

两个基线条件分别处理“一个列表已经取空”的情形，此时另一个列表的剩余部分已经有序，可以直接接上。每层递归至少消耗一个元素，所以最多递归 $|L1|+|L2|$ 次；merge([1, 4, 9], [10]) 返回 [1, 4, 9, 10]。

交互探索

展开斐波那契递归树，查看每个调用如何缩小到基线，以及相同子问题何时重复出现。

递归怎样分解到基线？

展开斐波那契递归树，比较输入规模和调用次数。