16: 递推

我们之前已经见到了方程可以用来组织,重复使用部分代码。我们也已经看到了方程可以根据其他方程被定义。在这节课中,我们会学习一个方程是如何根据自身被定义的!一种非常有用的方法叫做递推。有一句俗语:"为了理解递推,你首先要理解递推。"

范例

在关于循环的课程中,我们使用过while循环来创造下列输出。

5
4
3
2
1
Blastoff!
下面是一个使用递推的程序,能够取得相同的效果。

示例
使用递推倒数

让我们加一些额外的打印语句来帮助我们理解程序是如何工作的。这个程序的版本也从输入值读取时间期限。

示例
使用递推倒数
你可以在下面的框中输入程序的输入。

在上面的程序中使用输入,尝试其他输入值。先尝试0,看看会发生什么,然后尝试1

当输入是5,程序首先运行countdown方程。其中n=5,打印出5并运行countdown(4)。此操作重复进行,直到countdown(0)。最后打印出"Blastoff!",停止运行countdown。当Python以n=0结束countdown方程时,Python回到运行它的方程,也就是n=1时的方程countdown。然后我们回到n=2,以此类推。

我们也可以将递推代码可视化:

这个改变使得递推和我们所见过的方程不同。在这里,方程的几个不同版本在同一时间运行。换句话说,每次有超过一个的码框与这个同样的方程相对应。这与what we saw in the visualization where one function called another很相似,唯一的不同就是在这里被运行的方程和调用方程是同一个方程。注意,每一步只有"当前"变量(最新的/bottom-most frame)被使用。也就是说,非底端的部分"暂停",它们的值无法得到。

现在轮到你来写一些代码了。对countdown方程进行改动,使其变为从小数到大。

编程练习: Blast Up
编写一个递归方程countup(n),打印出'Blastoff!',然后分别在每一行出现数字1n提示

让我们再改变一下countdown,使得每次增量是2。那么输出应为5, 3, 1, Blastoff! 我们要改变一下方程的实参,把n-1改为n-2。除此以外还有什么需要改的么?

示例
尝试每次增量是2的倒数

这个程序并不像我们想象的那样运行。程序打印出5, 3, 1,这没问题。但是还会继续打印出-1, -3, -5,永无止境。(更具体来说,它会运行下去,直到没有时间和储存容量,因为每调用一次递推就会多占用一些运行容量;详见和可视化程序中一样的例子。)

在设计一个递推方程的时候,我们一定要注意调用顺序,避免设计成永远运行!再次更改上面的countdownBy2程序,让它正确地停在1(或2,如果n是偶数)并打印出'Blastoff!'。

编程练习: Double Time
改动此递推程序,使其正确地以增量2倒数。

设计递推方程

递推方程本质上是一个调用自身的方程。但是一定会有调用不了自身的情况,或者说程序会永远运行下去。比如上面的那个例子。基本案例是递推方程的一个不会自身调用的部分。在上面的那个例子中,基本案例是n<=0。设计一个递推方程需要谨慎地选择基本案例,以此确保方程的每一步最后都能够达到基本案例。

在下面的练习中,基本案例已经为你准备好了,但是剩余的部分需要你来编写。

编程练习: 数字的和
一个数n数字的和是组成这个数的每一个数字的和。编写一个递归方程digitalSum(n),使得输入一个正整数n,返还它的数字的和。比如,digitalSum(2019)应该返还12,因为2+0+1+9=12。提示 #1 提示 #2

现在写一个递推方程,将digitalSum作为子程序。

编程练习: 数字根
一个非负整数n的数字根是以如下方式计算的。从将组成n的数字相加开始,得到的数字再次进行数字的相加,直到获得一个一位数。比如说,2019的数字和是3,因为2+0+1+9=12,1+2=3。编写一个递推方程digitalRoot(n),返还n的数字根。

假设已有digitalSum方程。

习题

简答练习: GCD
下列递推程序的输出是什么?

def gcd(a, b):
  if b == 0: return a
  return gcd(b, a % b)
print(gcd(20, 12))
正确!此程序非常短,能够计算两个数字的最大约数。这也被叫做欧几里德算法,是最古老的算法之一。

编程练习: Hailstone
一个以正整数n 开始的冰雹
序列是按照如下两个简单规则生成的。如果n是偶数,序列中下一项是n/2。如果n是奇数,序列中下一项是3*n+1。重复该步骤,我们就得到了冰雹序列。编写一个递推方程hailstone(n),打印从n开始的冰雹序列。直到序列中的某一项得到1时停止(因为如果不停止,我们就会循环1, 4, 2, 1, 4, 2, ...)
比如,当n=5,程序应该输出下列序列:

5
16
8
4
2
1

数学家们认为,每一个冰雹序列最后都会达到1,不论n值开始为多少。然而,还没有人能证明这个定理。

嵌套序列

下面是一个递推循环的应用。嵌套序列是指将一些序列放在另一些序列里面,不论重复次数。比如,有关整数的嵌套序列是[[1, 2], [9, 10]][[1], 2]x = [[1], 2, [3, [[4]]]]。最后一个嵌套序列是一个拥有三项的序列:x[0]==[1]是第一项,x[1]==2是第二项,x[2]==[3, [[4]]]是最后一项(所以x是一个长度为3的序列)。注意,一个类似于[1, 2, 3]的序列也被认为是嵌套序列。我们是否能写一个方程,计算出任何嵌套序列的整数的和么?比如,输入值是[[5], 2, [10, 8, [[7]]]]的话,输出值就应该是32

这个任务如果用while循环或for循环就有些难,因为我们想要一个能处理任何形式的嵌套序列的方程。然而,嵌套序列有一个递推结构:一个嵌套序列是一个序列,序列中的每一项要么是(a)一个整数,要么是(b)一个嵌套序列。并且,一旦我们计算每个主序列中的一部分的和时,这些值的和也就是总和。下列代码可用来表达上述所说;isinstance(x, int)会给出一个布尔值,告诉我们x是否是一个整数(或序列)。

示例: 嵌套序列求和
运用递推方程计算一个嵌套序列中所有项的和。点击Run就可看到该方程在一些测试中的输出。
在下方输入测试语句,例如 print(myfunction("test argument"))

递推用来将每个嵌套序列化为更小的部分。比如说,nestedListSum([1, [3, 4], 5])总共会执行6次递推调用;第一次;然后是1;然后是[3, 4];然后是3;然后是4(然后[3, 4]的和是7);最后是5(然后总和是13)。这与在可视化窗口中的程序是一样的。

编程练习: 搜索一个嵌套序列
通过编写类似于nestedListSum的程序,定义一个递推方程

nestedListContains(NL, target)
,其中NL是一个由整数组成的嵌套序列,target是一个整数。该方程需要表明嵌套序列中是否存在target。也就是说,当target确实存在,返还布尔值True;当target不存在,返还False
比如,nestedListContains([1, [2, [3], 4]], 3)应该返还TruenestedListContains([1, [2, [3], 4]], 5)应该返还False

规则

递推和不规则图形有关--图片由多个小图片组成。这个网页的顶端的横幅就是一个例子。下一个练习题是通过递推创造一个简单的重复形式。

综合练习: 分尺
整理行的顺序来创建一个程序,输出尺子状的图案。比如,当n=3时,程序应输出下列设计。

-
--
-
---
-
--
-
  • if n == 1:
  • print(n * '-')
  • def ruler(n):
  • print('-')
  • ruler(n - 1)
  • else:
  • ruler(n - 1)

恭喜!你可以进行下一课的学习。