1.7 递归函数

INFO

译者：mancuoj、clcs

来源：1.7 Recursive Functions

对应：Disc 03、HW 03

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

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

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

在这种情况下，运算符 % 和 // 可以用来将一个数字分成两部分：最后一位数字和除去最后一位之外的其余部分。

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

18117 的各位数字之和是 $1+8+1+1+7=18$。同样地，我们也可以把这个和再拆分成最后一位 7 和前面部分的和 $1+8+1+1=11$。

这种拆分为我们提供了一种算法：要计算 n 的各位数字和，就把 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. 创建一个局部帧，n 绑定到 738，并在以此帧为起点的环境中执行函数体
2. 由于 738 不小于 10，会执行第 4 行的赋值语句，将 738 拆成 73 和 8
3. 在返回语句中，对当前环境中 all_but_last 的值 73 调用 sum_digits
4. 创建另一个将 n 绑定到 73 的局部帧，在这个以新帧为起点的新环境中再次执行函数体
5. 73 也不小于 10，拆成 7 和 3，对 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 语句实现的自然迭代版本是逐步累乘：

>>> 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，并把其中的 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 的正整数的和，并且按递增顺序排列的方法数。例如，使用最大为 4 的部分对 6 进行分割的方法数为 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 的部分以及不使用这部分的可能性。第一次和第二次递归调用即对应着这些可能性。

如果不使用递归来实现这个函数，将会复杂得多。鼓励感兴趣的读者尝试一下。