> For the complete documentation index, see [llms.txt](https://zlt-shadow.gitbook.io/sicp-in-python-cn/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zlt-shadow.gitbook.io/sicp-in-python-cn/di-1-zhang-yong-han-shu-gou-jian-chou-xiang/untitled.md). # 1.7 递归函数 如果函数体直接或间接地调用函数本身，则称为递归函数。 也就是说，执行递归函数体的过程可能需要再次应用该函数。 递归函数在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 ``` 利用我们的环境计算模型，我们可以准确地理解[这个递归函数](http://composingprograms.com/tutor.html#code=def+sum_digits\(n\)%3A%0A++++if+n+%3C+10%3A%0A++++++++return+n%0A++++else%3A%0A++++++++all_but_last,+last+%3D+n+//+10,+n+%25+10%0A++++++++return+sum_digits\(all_but_last\)+%2B+last%0A%0Asum_digits\(738\))是如何成功地应用的。不需要新的规则。 ![](/files/-MXNBn2foQIQajItQdNY) 在执行def语句时，名称sum\_digits被绑定到一个新函数，但该函数的函数体尚未执行。因此，sum\_digits的循环性质还不是问题。然后，在738上调用sum\_digits: 1. 为sum\_digits创建一个n绑定到738的本地框架，并在以该框架开始的环境中执行sum\_digits的主体。 2. 因为738不小于10，所以执行第4行上的赋值语句，将738分成73和8。 3. 在下面的return语句中，在当前环境中all\_but\_last的值73上调用了sum\_digits。 4. 为sum\_digits创建了另一个本地框架，这次将n绑定到73。 sum\_digits的主体将再次在以该帧开始的新环境中执行。 5. 因为73也不小于10,73被分成7和3，并且在7上调用sum\_digits, 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 递归函数的剖析 在许多递归函数体中可以找到一个常见的模式。 主体以基本情况开始，这是一个条件语句，它定义了对于最容易处理的输入函数的行为。 在sum\_digits的情况下，基本情况是任何单个数字参数，我们只需返回该参数。有些递归函数会有多个基本情况。 基本用例之后是一个或多个递归调用。 递归调用总是有一个特定的特征:它们简化了原来的问题。 递归函数通过增量地简化问题来表示计算。 例如，7的数字加起来比73的数字加起来简单，73的数字加起来又比738的数字加起来简单。 对于每一个后续调用，需要完成的工作就更少了。 递归函数通常用不同于我们以前使用的迭代方法的方法来解决问题。 考虑一个函数事实来计算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 ``` 另一方面，阶乘的递归实现可以用事实(n-1)表示事实(n)，这是一个更简单的问题。递归的基本情况是问题的最简单形式:fact(1)是1。 这两个阶乘函数在概念上不同。 迭代函数通过逐项相乘，构造从基本情况1到最终总数的结果。 另一方面，递归函数直接从最后一项n和更简单的问题fact(n-1)的结果构建结果。 当递归通过事实函数的连续应用程序“展开”到越来越简单的问题实例时，最终将从基本情况开始构建结果。 递归结束时将参数1传递给fact；每次调用的结果取决于下一次调用，直到达到基本用例为止。 从阶乘数学函数的标准定义来看，这个递归函数的正确性很容易验证： ![](/files/-MXNDSaArL3V1AN55ndJ) 虽然我们可以使用我们的计算模型来展开递归，但把递归调用看作函数抽象通常会更清楚。 也就是说，我们不应该关心fact(n-1)在fact主体中是如何实现的; 我们应该相信它计算的是n-1的阶乘。 将递归调用视为功能抽象被称为信念的递归飞跃。 我们根据函数本身来定义函数，但只是在验证函数的正确性时相信更简单的情况将正确工作。 在这个例子中，我们相信事实(n-1)将正确计算(n-1)!; 我们只需要检查n! 如果这个假设成立，计算是正确的。 这样，验证递归函数的正确性就是归纳法证明的一种形式。 函数fact\_iter和fact也不同，因为前者必须引入两个额外的名称total和k，这在递归实现中是不需要的。 在一般情况下，迭代函数必须保持一些在整个计算过程中变化的局部状态。 在迭代的任何点上，该状态描述了已完成工作的结果和剩余工作量。 例如，当k为3,total为2时，还有两项需要处理，即3和4。 另一方面,事实的特征是它的单一参数n。计算的状态是完全包含在结构的环境,有返回值,总体的作用,并结合n不同的值在不同的帧而不是显式地跟踪k。 递归函数利用评估的规则调用表达式绑定名称值,通常避免迭代期间正确分配本地名称的麻烦。 因此，递归函数更容易正确定义。 然而，学习识别递归函数演变的计算过程当然需要实践。 ### 1.7.2 相互递归 当递归过程被两个相互调用的函数分割时，这些函数称为相互递归。作为例子，考虑以下非负整数的偶数和奇数的定义： * 一个数比奇数多一，它就是偶数 * 一个数比偶数多一，它就是奇数 * 0是偶数 使用这个定义，我们可以[实现相互递归函数](http://composingprograms.com/tutor.html#code=def+is_even\(n\)%3A%0A++++if+n+%3D%3D+0%3A%0A++++++++return+True%0A++++else%3A%0A++++++++return+is_odd\(n-1\)%0A%0Adef+is_odd\(n\)%3A%0A++++if+n+%3D%3D+0%3A%0A++++++++return+False%0A++++else%3A%0A++++++++return+is_even\(n-1\)%0A%0Aresult+%3D+is_even\(4\))来确定一个数是偶数还是奇数： ``` def is_even(n): if n == 0: return True else: return is_odd(n-1) def is_odd(n): if n == 0: return False else: return is_even(n-1) result = is_even(4) ``` 通过打破两个函数之间的抽象边界，相互递归函数可以转换为一个单一的递归函数。在本例中，可以将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): """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 ``` 在这个递归函数中，基本情况是一个打印出来的单位数字。否则，在两个print调用之间放置一个递归调用。 在递归调用之前表达基本用例并不是一个严格的要求。实际上，通过观察print(n)在条件语句的两个子句中重复，可以更简洁地表达这个函数，因此可以在它之前 ``` >>> def cascade(n): """Print a cascade of prefixes of n.""" print(n) if n >= 10: cascade(n//10) print(n) ``` 作为相互递归的另一个例子，考虑一个有n个初始鹅卵石的双人博弈。玩家轮流从桌子上拿走一颗或两颗石子，拿走最后一颗石子的玩家获胜。假设Alice和Bob玩这个游戏，每人都使用一个简单的策略： * Alice总是拿走一块石子 * 如果桌子上有偶数个石子，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 树递归 另一种常见的计算模式称为树递归，在树递归中，一个函数多次调用自己。作为一个例子，考虑计算[斐波那契数列](http://composingprograms.com/tutor.html#code=def+fib\(n\)%3A%0A++++if+n+%3D%3D+1%3A%0A++++++++return+0%0A++++if+n+%3D%3D+2%3A%0A++++++++return+1%0A++++else%3A%0A++++++++return+fib\(n-2\)+%2B+fib\(n-1\)%0A%0Aresult+%3D+fib\(6\))，其中每个数字都是前面两个数字的和。 ``` def fib(n): if n == 1: return 0 if n == 2: return 1 else: return fib(n-2) + fib(n-1) result = fib(6) ``` 与我们之前的尝试相比，这个递归定义非常吸引人:它完全反映了我们熟悉的斐波那契数列的定义。 一个有多个递归调用的函数被称为树递归，因为每个调用分支成多个更小的调用，每个调用又分支成更小的调用，就像树的分支从主干延伸到更小但更多。 我们已经能够定义一个函数来计算斐波那契数，而无需使用树递归。 事实上，我们之前的尝试更有效率，这是本文后面讨论的主题。 接下来，我们考虑一个问题，它的树递归解决方案实质上比任何迭代替代简单。 ### 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)，它返回n个不同分区的数目，使用的部分最多为m。根据以下观察，这个函数有一个简单的树递归函数解决方案：用最多等于m的整数划分n个分区的方法 1. 用小于等于m的整数划分n-m 2. 用小于等于m-1的整数划分n-m的方法的数目。 要明白为什么这是正确的，观察所有的划分n的方法可以分为两组：那些至少包含一个m的和那些不包含m的。 并且，第一组中的每一个分区都是一个n-m的分区，最后加m。 在上面的示例中，前两个分区包含4，其余的分区不包含4。 因此，我们可以递归地将整数到m的划分问题简化为两个更简单的问题:(1)划分较小的数n-m，(2)划分较小的数到m-1。 为了完成实现，我们需要指定以下基本用例： 1. 有一种划分0的方法:不包含任何部分。 2. 有0种方法来划分- n。 3. 使用大小为0或小于0的部分对大于0的n进行分区有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的部分的可能性和不使用的可能性。第一次和第二次递归调用对应于这些可能性。 在不使用递归的情况下实现这个函数要复杂得多。有兴趣的读者请试一试。