1.7 递归函数

INFO

来源：1.7 Recursive Functions

如果一个函数的函数体直接或间接地调用了函数自身，这个函数就叫递归（recursive）函数。也就是说，执行递归函数函数体的过程，本身可能又需要再次施加这个函数。

在 Python 里，递归函数不用任何特殊语法，但理解和编写它们确实需要一些思考和练习。

我们从一个示例问题开始：写一个函数，求一个自然数各位数字之和。设计递归函数时，我们会寻找把一个问题分解成更简单问题的办法。

在这里，运算符 % 和 // 可以把一个数字拆成两部分：最后一位数字，以及除去最后一位之外的其余部分。

>>> 18117 % 10
7
>>> 18117 // 10
1811

18117 的各位数字之和是 $1+8+1+1+7=18$。既然数字可以这样拆开，这个和也可以拆成最后一位 7 和前面部分的和 $1+8+1+1=11$。

这种拆分给出了一种算法：要计算 n 的各位数字之和，就把它的最后一位 n % 10 加上 n // 10 的各位数字之和。只有一个特殊情况：数字只有一位时，它的各位数字之和就是它自己。

这个算法可以用递归函数来实现：

>>> def sum_digits(n):
        """返回正整数 n 的各位数字之和"""
        if n < 10:
            return n
        else:
            all_but_last, last = n // 10, n % 10
            return sum_digits(all_but_last) + last

即使函数体内部调用了 sum_digits 自身，这个定义依然完整且正确。求一个数各位数字之和的问题被拆成两步：先求除最后一位之外所有数字之和，再加上最后一位。这两步都比原问题简单。

这个函数之所以是递归的，是因为第一步（也就是 sum_digits(all_but_last)）与原问题属于同一类问题。也就是说，要实现 sum_digits，需要的正是 sum_digits 本身。

>>> sum_digits(9)
9
>>> sum_digits(18117)
18
>>> sum_digits(9437184)
36
>>> sum_digits(11408855402054064613470328848384)
126

用我们之前建立的环境模型，可以精确理解这个递归函数是如何成功应用的，而且不需要任何新规则。

执行 def 语句时，名称 sum_digits 被绑定到一个新函数上，但该函数的函数体还没有执行。因此，sum_digits 的循环特性（circular nature）暂时还不是问题。接着我们调用 sum_digits(738)：

1. 创建一个 sum_digits 的局部帧，n 绑定到 738，并在以这个帧为起点的环境中执行函数体。
2. 由于 738 不小于 10，执行第 4 行的赋值语句，把 738 拆成 73 和 8。
3. 在接下来的返回语句中，对当前环境中 all_but_last 的值 73 调用 sum_digits。
4. 再创建一个 sum_digits 的局部帧，这次 n 绑定到 73，并在以新帧为起点的环境中再次执行函数体。
5. 73 也不小于 10，于是拆成 7 和 3，对在这个帧里求得的 all_but_last 的值 7 调用 sum_digits。
6. 创建第三个局部帧，n 绑定到 7。
7. 在从这个帧开始的环境中，n < 10 成立，因此返回 7。
8. 回到第二个局部帧，把返回值 7 与 last 的值 3 相加，返回 10。
9. 回到第一个局部帧，把返回值 10 与 last 的值 8 相加，返回 18。

---

这个递归函数虽然有循环调用的特性，却能正确应用，因为它被应用了两次，而每次的参数都不同。而且，第二次应用是比第一次更简单的数字求和问题实例。生成调用 sum_digits(18117) 的环境图，就能看到每次连续的 sum_digits 调用用的参数都比上一次更小，直到最后遇到个位数的输入。

这个例子也说明，函数体简单的函数可以借助递归演化出复杂的计算过程。

1.7.1 递归函数剖析

许多递归函数的函数体里都有一种共同的模式：

• 函数体从一个基准情况（base case）开始：用条件语句定义函数在「最简单、最容易处理」的输入上的行为。对 sum_digits 来说，基准情况是任意个位数的参数，直接返回它即可。有些递归函数会有多个基准情况。
• 基准情况之后是一个或多个递归调用。递归调用总有一个共同特征：它们让原问题变得更简单。递归函数靠逐步简化问题来表达计算。例如，求 7 的各位数字之和比求 73 的简单，求 73 的又比求 738 的简单。每做一次递归调用，剩下的工作量就少一些。

递归函数解决问题的方式，往往和我们之前用的迭代方法不同。看计算 n 的阶乘的函数 fact，比如 fact(4) 会算出 $4!=4\cdot 3\cdot 2\cdot 1=24$ 。

一种自然的迭代实现用 while 语句，把直到 n 的每个正整数逐个乘进总数：

>>> def fact_iter(n):
        total, k = 1, 1
        while k <= n:
            total, k = total * k, k + 1
        return total

>>> fact_iter(4)
24

另一方面，阶乘的递归实现可以用 fact(n-1)（一个更简单的问题）来表达 fact(n)。这个递归的基准情况是问题的最简单形式：fact(1) 等于 1。

这两个阶乘函数在概念上不同。迭代函数从基准情况 1 出发，逐项相乘，一直乘到最终总数，由此构建结果。相反，递归函数直接用最后一项 n 和更简单问题 fact(n-1) 的结果来构建结果。

随着递归沿着 fact 函数对越来越简单的问题实例的一次次应用而展开（unwinds），结果最终从基准情况开始构建出来。递归以把参数 1 传给 fact 结束；每个调用的结果都依赖下一次调用，直到抵达基准情况。

从阶乘的标准数学定义，很容易验证这个递归函数的正确性：

$$\begin{array}{rl}(n-1)!& =(n-1)\cdot (n-2)\cdots \cdots 1\\ n!& =n\cdot (n-1)\cdot (n-2)\cdots \cdots 1\\ n!& =n\cdot (n-1)!\end{array}$$

虽然我们可以借助计算模型把递归展开，但把递归调用看成函数抽象，通常更容易理解。也就是说，我们不必关心 fact(n-1) 在 fact 的函数体里是怎么实现的；只要相信它算出了 n-1 的阶乘就行。把递归调用当作函数抽象，叫作递归的信仰之跃（recursive leap of faith）。我们用函数自身来定义函数，但在验证它的正确性时，只需相信更简单的情况同样能正确工作。

在这个例子里，我们相信 fact(n-1) 能正确算出 $(n-1)!$；只要这个假设成立，我们只需检查 $n!$ 是否算对。这样验证递归函数的正确性，就是一种归纳法（induction）证明。

函数 fact_iter 和 fact 还有一个区别：前者必须引入两个额外的名称 total 和 k，而递归实现不需要。一般来说，迭代函数必须维护一些在计算过程中变化的局部状态。迭代进行到任何时刻，这个状态都刻画了已经完成的工作和剩余的工作量。例如，当 k = 3、total = 2 时，说明还有两项（3 和 4）待处理。反过来，fact 只靠单一参数 n 就刻画了它的状态。计算的全部状态都装在环境结构里：返回值层层传递，扮演了 total 的角色；n 在不同的帧里绑定到不同的值，而不必显式追踪 k。

递归函数利用了调用表达式的求值规则——也就是把名称绑定到值的规则，往往省去了迭代时还得正确维护局部变量的麻烦。因此，递归函数通常更容易定义正确。不过，要学会辨认递归函数演化出的计算过程，确实需要多练习。

1.7.2 互递归

当一个递归过程被分到两个互相调用的函数里时，我们就说这两个函数是互递归的（mutually recursive）。

例如，考虑以下非负整数的偶数和奇数定义：

• 如果一个数比一个奇数大 1，那它就是偶数
• 如果一个数比一个偶数大 1，那它就是奇数
• 0 是偶数

用这个定义，我们可以实现互递归函数，判断一个数是偶数还是奇数：

互递归的函数其实可以改写成单个递归函数，只要打破两个函数之间的抽象界限即可。拿这个例子来说，可以把 is_odd 的函数体并入 is_even 的函数体，同时记得把 is_odd 里的 n 换成 n-1，以对应传进去的参数：

>>> def is_even(n):
        if n == 0:
            return True
        else:
            if (n-1) == 0:
                return False
            else:
                return is_even((n-1)-1)

所以，互递归并不比简单递归更神秘或更强大，它只是提供了一种机制，让复杂的递归程序仍能保持抽象。

1.7.3 递归函数中的打印

递归函数演化出的计算过程，往往可以用 print 调用来可视化。

作为示例，我们来实现一个 cascade 函数，它按从大到小再到大的顺序打印一个数字的所有前缀：

>>> def cascade(n):
        """打印 n 的前缀级联"""
        if n < 10:
            print(n)
        else:
            print(n)
            cascade(n//10)
            print(n)

>>> cascade(2013)
2013
201
20
2
20
201
2013

在这个递归函数里，基准情况是个位数，直接打印。否则，就把递归调用放在两次 print 调用之间。

基准情况并不硬性要求写在递归调用前面。其实，只要注意到 print(n) 在条件语句的两个分支里都出现了，就能把这个函数写得更紧凑——把它提到前面即可：

>>> def cascade(n):
        """打印 n 的前缀级联"""
        print(n)
        if n >= 10:
            cascade(n//10)
            print(n)

作为互递归的另一个例子，考虑一个双人游戏：桌上最初有 n 个石子，玩家轮流拿走一个或两个石子，拿走最后一颗石子的人获胜。假设 Alice 和 Bob 玩这个游戏，两人各用一种简单策略：

• Alice 总是拿走一个石子
• 如果桌子上有偶数个石子，Bob 就拿走两个；否则拿走一个

给定 n 个初始石子且 Alice 先手，谁会赢得游戏？

这个问题的一种自然分解方式，是把每种策略各自封装成一个函数。这样，修改一种策略不会影响另一种，两者之间的抽象屏障（abstraction barrier）得以保持。为了体现游戏回合制的特点，这两个函数在每一回合结束时互相调用。

>>> def play_alice(n):
        if n == 0:
            print("Bob wins!")
        else:
            play_bob(n-1)

>>> def play_bob(n):
        if n == 0:
            print("Alice wins!")
        elif is_even(n):
            play_alice(n-2)
        else:
            play_alice(n-1)

>>> play_alice(20)
Bob wins!

在 play_bob 里，我们看到函数体中可能出现多个递归调用。不过在这个例子中，每次调用 play_bob 最多只会调用一次 play_alice。下一节我们会讨论：单个函数调用直接产生多个递归调用时，会发生什么。

1.7.4 树形递归

另一种常见的计算模式叫树形递归（tree recursion）：一个函数调用自己不止一次。

例如计算斐波那契数列，其中每个数都是前两个数之和。

与我们之前的尝试相比，这个递归定义极具吸引力：它与人们熟悉的斐波那契数定义完全吻合。有多个递归调用的函数叫作树形递归，因为每次调用都会分叉出多个更小的调用，每个更小的调用又分叉出更小的调用，就像树枝从树干伸出，越伸越细、越伸越多。

我们之前已经能定义一个不用树形递归的函数来计算斐波那契数。事实上，之前的做法更高效，这个话题文中稍后会讨论。接下来，我们考虑这样一个问题：它的树形递归解法比任何迭代方案都简单得多。

1.7.5 示例：分割数

正整数 n 使用不超过 m 的部分的分割数，是指把 n 表示成若干不超过 m 的正整数之和（按递增顺序排列）的方法数。例如，把 6 用不超过 4 的部分分割，方法数为 9。

1.  6 = 2 + 4
2.  6 = 1 + 1 + 4
3.  6 = 3 + 3
4.  6 = 1 + 2 + 3
5.  6 = 1 + 1 + 1 + 3
6.  6 = 2 + 2 + 2
7.  6 = 1 + 1 + 2 + 2
8.  6 = 1 + 1 + 1 + 1 + 2
9.  6 = 1 + 1 + 1 + 1 + 1 + 1

我们将定义一个名为 count_partitions(n, m) 的函数，返回用不超过 m 的部分对 n 进行不同分割的方法数。基于以下观察，作为树形递归函数，它有一个简单的解法：

用不超过 m 的整数分割 n 的方法数，等于：

1. 用不超过 m 的整数分割 n-m 的方法数，加上
2. 用不超过 m-1 的整数分割 n 的方法数。

要弄清它为什么成立，可以注意：n 的所有分割方式可以分成两组——至少含一个 m 的，和不含 m 的。而且，第一组里的每种分割，都是对 n-m 的一种分割，最后再补上一个 m。在上面的例子里，前两种分割含 4，其余的不含。

因此，我们可以把「用不超过 m 的整数分割 n」递归地归约为两个更简单的问题：① 分割一个更小的数 n-m，② 用更小的部分（不超过 m-1）来分割。

要实现它，还需要指定以下基准情况：

1. 整数 0 只有一种分割方法：不取任何部分。
2. 负整数 n 无法分割，有 0 种方法。
3. 任何大于 0 的 n，用 0 或更小的部分分割，方法数都是 0。

>>> def count_partitions(n, m):
        """计算使用最大数 m 的整数分割 n 的方法数"""
        if n == 0:
            return 1
        elif n < 0:
            return 0
        elif m == 0:
            return 0
        else:
            return count_partitions(n-m, m) + count_partitions(n, m-1)

>>> count_partitions(6, 4)
9
>>> count_partitions(5, 5)
7
>>> count_partitions(10, 10)
42
>>> count_partitions(15, 15)
176
>>> count_partitions(20, 20)
627

可以把树形递归函数看成在探索各种可能性。这里，我们探索的是「用一个大小为 m 的部分」和「不用」这两种可能，第一次和第二次递归调用就分别对应它们。

不用递归来实现这个函数，会复杂得多。感兴趣的读者不妨一试。