文档：1.7 Recursive Functions

参考：cs61a.org/spring2018

1.7 递归函数

如果函数的主体直接或间接地调用函数本身，则函数被称为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):
        """Return the sum of the digits of positive integer 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函数在其自身的内部被调用。 将一个数的每位数字相加的问题分为两个步骤：将除最后一位之外的所有数字相加，然后添加最后一位数字。 这两个步骤都比原问题简单。 该函数是递归的，因为第一步处理是与原问题相同的问题。 也就是说，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的循环性并不是问题。然后，sum_digits被在738上调用：

1. 创建一个n = 738的sum_digits的局部帧，sum_digits的主体在以该帧开始的环境中执行。
2. 由于738不小于10，执行第4行的赋值语句时，将738分解为73和8。
3. 在以下return语句中，sum_digits在73上调用，这是当前环境中的all_but_last的值。
4. 创建sum_digits的另一个局部帧，此时n被绑定到73上。 sum_digits的主体再次在以此帧开始的新环境中执行。
5. 由于73也不小于10，73被分为7和3，并且sum_digits在7上被调用，所以在此帧中计算all_but_last的值。
6. 创建sum_digits的第三个局部帧，其中n为7。
7. 在从这个帧开始的环境中，确定符合n <10，因此返回7。
8. 在第二个局部帧中，此返回值7与3相加，最后的值返回10。
9. 在第一个局部帧中，返回值10与最后一个值8相加，返回18。
   该函数的循环体，虽然被应用了两次，但每次都有一个不同的参数，所有这个递归函数调用正确。此外，第二次调用的数字求和问题是比第一次更简单的问题。我们生成调用sum_digits(18117)的环境图示，看到对sum_digits的每个连续调用都比上一个参数更小，直到最终达到单位数输入。

这个例子还说明了简单函数体如何通过使用递归来演化复杂的计算过程。

1.7.1 解剖递归函数

常见的模式可以在许多递归函数的体中找到。函数体以base case基线条件开始，它是一个定义了最简单处理输入函数的行为条件的语句。在sum_digits例子里面，base case基线条件是任何的单位数的参数，处理方法是返回该参数。一些递归函数可能会有多个base case基线条件。

base case基线条件之后是一个或多个递归调用。递归调用始终具有某种特性：它们能简化原始问题。递归函数通过逐步简化问题来表达计算过程。例如，将7的每位数字相加比把73的每位数字相加简单得多，而这又比对`738的每位数字求和更简单。对于每个后续调用，剩下的工作会越来越少。

递归函数解决问题的方式与之前的迭代方法完全不同。比如用函数fact计算n次阶乘，其中fact(4)计算结果为：4！= 4⋅3⋅2⋅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

由于递归通过将fact函数连续应用到更简单的问题实例中”展开“，结果最终从基线条件开始构建。整个递归体在将参数1传递给fact后结束; 每次调用的结果取决于下一次调用，直到符合基线条件。

这个递归函数的正确性很容易从递归的数学标准定义中进行验证：

1.7.2 相互递归

比如有一个函数f，里面调用了函数g，而函数g里面又调用了函数f。像这种函数f跟函数g，相互调用，那么我们就称这样的递归为相互递归 。例如，判断一个数是偶数，还是奇数就是一个最简单的相互递归。通过数学知识，我们很容易知道有以下的定义：

1. 如果一个数是奇数，那它的后一位数一定是偶数。
2. 如果一个数是偶数，那它的后一位数一定是奇数。
3. 0是偶数

使用这个定义，我们可以用相互递归的函数来判断数字是偶数还是奇数：

>>> 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 递归函数中的打印

通过递归函数演化的计算过程通常可以使用打印调用进行可视化。 例如，我们将实现一个函数cascade，它将数字的所有前缀从最大到最小，又从最小到最大打印出来。

>>> def cascade(n):
        """Print a cascade of prefixes of n."""
        if n < 10:
            print(n)
        else:
            print(n)
            cascade(n//10)
            print(n)
>>> cascade(2013)
2013
201
20
2
20
201
2013

cascade的另一种写法：

>>> def cascade(n):
        """Print a cascade of prefixes of n."""
        print(n)
        if n >= 10:
            cascade(n//10)
            print(n)

相互递归的另一个例子是一个双人游戏：最初在桌子上有n个鹅卵石；玩家轮流从桌子上移除一个或两个鹅卵石；移除最后一个鹅卵石的玩家获胜。 假设Alice和Bob玩这个游戏，他们每次都使用以下策略：

1.Alice每次都拿掉一个鹅卵石
2.如果桌子上的石头数量为偶数，Bob就会拿掉两个；不然，Bob只拿一个

如果鹅卵石初始值为n并且游戏由Alice开始，谁能赢比赛呢？

我们将每个策略封装在自己的函数中，这样能让我们在修改一个策略的同时不会影响另一个策略，维护了两者之间的抽象界限。 这个游戏是轮流进行的，这两个函数在每一回合结束时需要相互调用。

>>> 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 树形递归

另一种常见的计算模式称为树形递归，这种情况下函数自己调用不止一次。 例如，计算斐波那契数列，其中每个数字是前两个数的和。

相对于我们以前的尝试，这种递归定义更有吸引力：它完全反映了斐波纳契数列的定义。 具有多个递归调用的函数被称为树形递归，因为每个调用由多个较小的调用的分支组成，每个调用的分支又可以由更小的调用分支组成，正如树的分支一样。

我们之前已经能够定义一个函数来计算没有树形递归的斐波那契数列。 事实上，我们以前的方法更有效率，这是本文后面将讨论的主题。 接下来，我们将讨论为什么树形递归比任何替代的迭代方案简单得多。

1.7.5 示例：拆分

把正整数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)，返回值是正整数n的不同拆分方法的数量，其中每个拆分数不能大于m，即最大拆分数为m。 如下，该函数有树形递归的简单解决方案：

用m作为最大拆分数的n的拆分方法有：

1. 使用最大到m的正整数来拆分n-m的方式的数量，加上
2. 使用最大到m-1的正整数来拆分n的方式的数量。

来看看为什么这是真的，通过观察可以发现拆分n的方法可以分为两组：那些至少包括一个m的和那些完全不包含m的。 此外，第一组中的每个拆分方法是n-m的拆分，之后再加上m。 在上面的例子中，前两个拆分法包含4，其余的不包含。

因此，我们把问题简化成两步：（1）拆分更小的数n-m，（2）使用最大为m-1的数来进行拆分。

要完成函数实现，我们需要指定以下基线条件：
1.拆分0的方式只有一种：不包括任何部分
2.拆分负数n的方式有0种。
3.拆分任何大于0的n但是用小于等于0作为组成部分的分割方式只有0种。

>>> def count_partitions(n, m):
        """Count the ways to partition n using parts up to m."""
        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的大小的可能性以及不可用作拆分的可能性。第一以及第二个递归调用对应这些可能性。

用非递归方式实现这个函数需要更多的投入，我们鼓励感兴趣的读者多多尝试。