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

范例

在关于循环的课程中，我们使用过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!'，然后分别在每一行出现数字1到n。提示

你需要创建一个账号并登录才能问一个问题。

def countdown(n): if n == 0: print('Blastoff!') else: print(n) countdown(n - 1)

更多的动作... 重置代码至默认 帮助

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

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

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

编程练习: Double Time

改动此递推程序，使其正确地以增量2倒数。

你需要创建一个账号并登录才能问一个问题。

def countdownBy2(n): if n == 0: print('Blastoff!') else: print(n) countdownBy2(n - 2)

更多的动作... 重置代码至默认 帮助

设计递推方程

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

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

编程练习: 数字的和

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

你需要创建一个账号并登录才能问一个问题。

def digitalSum(n): if n < 10: return n else: # recursive case

更多的动作... 重置代码至默认 帮助

现在写一个递推方程，将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是否是一个整数（或序列）。

递推用来将每个嵌套序列化为更小的部分。比如说，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)应该返还True，nestedListContains([1, [2, [3], 4]], 5)应该返还False。

你需要创建一个账号并登录才能问一个问题。

更多的动作... 帮助

规则

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

综合练习: 分尺

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

-
--
-
---
-
--
-

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

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