第4章：递归

思考并回答以下问题：

本章涵盖：

本章目标

• 理解某些复杂的难题为何可以通过简单的递归解决。
• 学习如何构建递归程序。
• 理解和应用递归三原则。
• 从循环的角度理解递归。
• 实现问题的递归解法。
• 理解计算机系统如何实现递归。

何谓递归

递归是解决问题的一种方法，它将问题不断地分成更小的子问题，直到子问题可以用普通的方法解决。通常情况下，递归会使用一个不停调用自己的函数。尽管表面上看起来很普通，但是递归可以帮助我们写出非常优雅的解决方案。对于某些问题，如果不用递归，就很难解决。

计算一列数之和

我们从一个简单的问题开始学习递归。即使不用递归，我们也知道如何解决这个问题。假设需要计算数字列表[1, 3, 5, 7, 9]的和。代码清单4-1展示了如何通过循环函数来计算结果。这个函数使用初始值为0的累加变量theSum，通过把列表中的数加到该变量中来计算所有数的和。

代码清单4-1 循环求和函数

def listsum(numList):
	theSum = 0
	for i in numList:
		theSum = theSum + i
	return theSum

假设暂时没有while循环和for循环。应该如何计算结果呢？如果你是数学家，就会记得加法是接受两个参数（一对数）的函数。将问题从求一列数之和重新定义成求数字对之和，可以将数字列表重写成完全括号表达式，例如((((1 + 3) + 5) + 7) + 9)。该表达式还有另一种添加括号的方式，即(1 + (3 + (5 + (7 + 9))))。注意，最内层的括号对(7 + 9)不用循环或者其他特殊语法结构就能直接求解。事实上，可以使用下面的简化步骤来求总和。

总和 = (1 + (3 + (5 + (7 + 9))))
总和 = (1 + (3 + (5 + 16)))
总和 = (1 + (3 + 21))
总和 = (1 + 24)
总和 = 25

如何将上述想法转换成Python程序呢？让我们用Python列表来重新表述求和问题。数字列表numList的总和等于列表中的第一个元素（numList[0]）加上其余元素（numList[1:]）之和。可以用函数的形式来表述这个定义。

$listSum(numList)=first(numList)+listSum(rest(numList))$

first(numList)返回列表中的第一个元素，rest(numList)则返回其余元素。用Python可以轻松地实现这个等式，如代码清单4-2所示。

代码清单4-2 递归求和函数

def listsum(numList):
	if len(numList) == 1:
		return numList [0]
	else:
		return numList[0] + listsum(numList[1:])

在这一段代码中，有两个重要的思想值得探讨。首先，第2行检查列表是否只包含一个元素。这个检查非常重要，同时也是该函数的退出语句。对于长度为1的列表，其元素之和就是列表中的数。其次，listsum函数在第5行调用了自己！这就是我们将listsum称为递归函数的原因——递归函数会调用自己。

图4-1展示了在求解[1, 3, 5, 7, 9]之和时的一系列递归调用。我们需要将这一系列调用看作一系列简化操作。每一次递归调用都是在解决一个更小的问题，如此进行下去，直到问题本身不能再简化为止。

图4-1 求和过程中的递归调用

当问题无法再简化时，我们开始拼接所有子问题的答案，以此解决最初的问题。图4-2展示了listsum函数在返回一系列调用的结果时进行的加法操作。当它返回到顶层时，就有了最终答案。

图4-2 求和过程中的一系列返回操作

递归三原则

正如阿西莫夫提出的机器人三原则一样，所有的递归算法都要遵守三个重要的原则：

(1) 递归算法必须有基本情况；

(2) 递归算法必须改变其状态并向基本情况靠近；

(3) 递归算法必须递归地调用自己。

让我们来看看listsum算法是如何遵守上述原则的。基本情况是指使算法停止递归的条件，这通常是小到足以直接解决的问题。listsum算法的基本情况就是列表的长度为1。

为了遵守第二条原则，必须设法改变算法的状态，从而使其向基本情况靠近。改变状态是指修改算法所用的某些数据，这通常意味着代表问题的数据以某种方式变得更小。listsum算法的主数据结构是一个列表，因此必须改变该列表的状态。由于基本情况是列表的长度为1，因此向基本情况靠近的做法自然就是缩短列表。这正是代码清单4-2的第5行所做的，即在一个更短的列表上调用listsum。

最后一条原则是递归算法必须对自身进行调用，这正是递归的定义。对于很多新手程序员来说，递归是令他们颇感困惑的概念。新手程序员知道如何将一个大问题分解成众多小问题，并通过编写函数来解决每一个小问题。然而，递归似乎让他们落入怪圈：有一个需要用函数来解决的问题，但是这个函数通过调用自己来解决问题。其实，递归的逻辑并不是循环，而是将问题分解成更小、更容易解决的子问题。

接下来，我们会讨论更多的递归例子。在每一个例子中，我们都会根据递归三原则来构建问题的解决方案。

将整数转换成任意进制的字符串

假设需要将一个整数转换成以2~16为基数的字符串。例如，将10转换成十进制字符串”10”，或者二进制字符串”1010”。尽管很多算法都能解决这个问题，包括3.3.6节讨论的算法，但是递归的方式非常巧妙。

以十进制整数769为例。假设有一个字符序列对应前10个数，比如convString = “0123456789”。若要将一个小于10的数字转换成其对应的字符串，只需在字符序列中查找对应的数字即可。例如，9对应的字符串是convString[9]或者”9”。如果可以将整数769拆分成7、6和9，那么将其转换成字符串就十分简单。因此，一个很好的基本情况就是数字小于10。

上述基本情况说明，整个算法包含三个组成部分：

(1) 将原来的整数分成一系列仅有单数位的数；

(2) 通过查表将单数位的数转换成字符串；

(3) 连接得到的字符串，从而形成结果。

接下来需要设法改变状态并且逐渐向基本情况靠近。思考哪些数学运算可以缩减整数，最有可能的是除法和减法。虽然减法可能有效，但是我们并不清楚应该减去什么数。让我们来看看将需要转换的数字除以对应的进制基数会如何。

将769除以10，商是76，余数是9。这样一来，我们便得到两个很好的结果。首先，由于余数小于进制基数，因此可以通过查表直接将其转换成字符串。其次，得到的商小于原整数，这使得我们离基本情况更近了一步。下一步是将76转换成对应的字符串。再一次运用除法，得到商7和余数6。问题终于被简化到将7转换成对应的字符串，由于它满足基本情况n<\bast（其中bast为10），因此转换过程十分简单。图4-3展示了这一系列的操作。注意，我们需要记录的数字是右侧方框内的余数。

图4-3　将整数转换成十进制字符串

代码清单4-3展示的Python代码实现了将整数转换成以2~16为进制基数的字符串。

代码清单4-3　将整数转换成以2~16为进制基数的字符串

1.
2.  def toStr(n, base):
3.      convertString = "0123456789ABCDEF"
4.      if n < base:
5.         return convertString[n]
6.      else:
7.         return toStr(n//base, base) + convertString[n%base]

第4行检查是否为基本情况，即n小于进制基数。如果是，则停止递归并且从convertString中返回字符串。第7行通过递归调用以及除法来分解问题，以同时满足第二条和第三条原则。

来看看该算法如何将整数10转换成其对应的二进制字符串”1010”。

图4-4展示了结果，但是看上去数位的顺序反了。由于第7行首先进行递归调用，然后才拼接余数对应的字符串，因此程序能够正确工作。如果将convertString查找和返回toStr调用反转，结果字符串就是反转的。但是将拼接操作推迟到递归调用返回之后，就能得到正确的结果。说到这里，你应该能想起第3章讨论的栈。

图4-4　将整数10转换成二进制字符串

栈帧：实现递归

假设不拼接递归调用toStr的结果和convertString的查找结果，而是在进行递归调用之前把字符串压入栈中。代码清单4-4展示了修改后的实现。

代码清单4-4　把字符串压入栈中

1.  rStack = Stack()
2.
3.  def toStr(n, base):
4.      convertString = "0123456789ABCDEF"
5.      if n < base:
6.         rStack.push(convertString[n])
7.      else:
8.         rStack.push(convertString[n % base])
9.         toStr(n // base, base)

每一次调用toStr，都将一个字符压入栈中。回到之前的例子，可以发现在第四次调用toStr之后，栈中内容如图4-5所示。因此，只需执行出栈操作和拼接操作，就能得到最终结果”1010”。

图4-5　栈中内容

这个例子展示了Python如何实现递归函数调用。当调用函数时，Python分配一个栈帧来处理该函数的局部变量。当函数返回时，返回值就在栈的顶端，以供调用者访问。图4-6展示了返回语句之后的调用栈。

图4-6　调用栈示例

注意，调用toStr(2//2, 2)将返回值”1”放在栈的顶端。之后，这个返回值被用来替换对应的函数调用（toStr(1, 2)）并生成表达式”1” + convertString[2%2]。这一表达式会将字符串”10”留在栈顶。通过这种方法，Python的调用栈取代了代码清单4-4显式使用的栈。在计算一列数之和的例子中，可以认为栈中的返回值取代了累加变量。

栈帧限定了函数所用变量的作用域。尽管反复调用相同的函数，但是每一次调用都会为函数的局部变量创建新的作用域。

如果记住栈的这种思想，就会发现递归函数写起来很容易。

递归可视化

前文探讨了一些能用递归轻松解决的问题。但是，要想象递归的样子或者将递归过程可视化仍然十分困难。这使得递归难以掌握。本节将探讨一系列使用递归来绘制有趣图案的例子。看着这些图案一点一点地形成，你会对递归过程有新的认识，从而深刻地理解递归的概念。

我们将使用Python的turtle模块来绘制图案。Python的各个版本都提供turtle模块，它用起来非常简便。顾名思义，可以用turtle模块创建一只小乌龟（turtle）并让它向前或向后移动，或者左转、右转。小乌龟的尾巴可以抬起或放下。当尾巴放下时，移动的小乌龟会在其身后画出一条线。若要增加美观度，可以改变小乌龟尾巴的宽度以及尾尖所蘸墨水的颜色。

让我们通过一个简单的例子来展示小乌龟绘图的过程。使用turtle模块递归地绘制螺旋线，如代码清单4-5所示。先导入turtle模块，然后创建一个小乌龟对象，同时也会创建用于绘制图案的窗口。接下来定义drawSpiral函数。这个简单函数的基本情况是，要画的线的长度（参数len）降为0。如果线的长度大于0，就让小乌龟向前移动len个单位距离，然后向右转90度。递归发生在用缩短后的距离再一次调用drawSpiral函数时。代码清单4-5在结尾处调用了myWin.exitonclick()函数，这使小乌龟进入等待模式，直到用户在窗口内再次点击之后，程序清理并退出。

代码清单4-5　用turtle模块递归地绘制螺旋线

1.   from turtle import *
2.
3.   myTurtle = Turtle()
4.   myWin = myTurtle.getscreen()
5.
6.   def drawSpiral(myTurtle, lineLen):
7.       if len > 0:
8.           myTurtle.forward(lineLen)
9.           myTurtle.right(90)
10.          drawSpiral(myTurtle, lineLen-5)
11.
12.  drawSpiral(myTurtle, 100)
13.  myWin.exitonclick()

理解了这个例子的原理，便能用turtle模块绘制漂亮的图案。接下来绘制一棵分形树。分形是数学的一个分支，它与递归有很多共同点。分形的定义是，不论放大多少倍来观察分形图，它总是有相同的基本形状。自然界中的分形例子包括海岸线、雪花、山岭，甚至树木和灌木丛。众多自然现象中的分形本质使得程序员能够用计算机生成看似非常真实的电影画面。下面来生成一棵分形树。

思考如何用分形来描绘一棵树。如前所述，不论放大多少倍，分形图看起来都一样。对于树木来说，这意味着即使是一根小嫩枝也有和一整棵树一样的形状和特征。借助这一思想，可以把树定义为树干，其上长着一棵向左生长的子树和一棵向右生长的子树。因此，可以将树的递归定义运用到它的左右子树上。

让我们将上述想法转换成Python代码。代码清单4-6展示了如何用turtle模块绘制分形树。仔细研究这段代码，会发现第5行和第7行进行了递归调用。第5行在小乌龟向右转了20度之后立刻进行递归调用，这就是之前提到的右子树。然后，第7行再一次进行递归调用，但这次是在向左转了40度以后。之所以需要让小乌龟左转40度，是因为它首先需要抵消之前右转的20度，然后再继续左转20度来绘制左子树。同时注意，每一次进行递归调用时，都从参数branchLen中减去一些，这是为了让递归树越来越小。第2行的if语句会检查branchLen是否满足基本情况。

代码清单4-6　绘制分形树

1.  def tree(branchLen, t):
2.      if branchLen > 5:
3.          t.forward(branchLen)
4.          t.right(20)
5.          tree(branchLen-15, t)
6.          t.left(40)
7.          tree(branchLen-10, t)
8.          t.right(20)
9.          t.backward(branchLen)

请执行分形树的代码，但在此之前，先想象一下绘制出来的树会是什么样。这棵树是如何开枝散叶的呢？程序是会同时对称地绘制左右子树，还是会先绘制右子树再绘制左子树？在输入tree函数的代码之后，可以用下面的代码来绘制一棵树。

>>> from turtle import *
>>> t = Turtle()
>>> myWin = t.getscreen()
>>> t.left(90)
>>> t.up()
>>> t.backward(300)
>>> t.down()
>>> t.color('green')
>>> tree(110, t)
>>> myWin.exitonclick()

注意，树上的每一个分支点都对应一次递归调用，而且程序先绘制右子树，并一路到其最短的嫩枝，如图4-7所示。接着，程序一路反向回到树干，以此绘制完右子树，如图4-8所示。然后，开始绘制左子树，但并不是一直往左延伸到最左端的嫩枝。相反，左子树自己的右子树被完全画好后才会绘制最左端的嫩枝。

图4-7　先绘制右子树

图4-8　分形树的右半部分

这个简单的分形树程序仅仅是一个开始。你会注意到，绘制出来的树看上去并不真实，这是由于自然界并不如计算机程序一样对称。在本章最后的练习中，你将探索如何绘制出看起来更真实的树。

谢尔平斯基三角形
另一个具有自相似性的分形图是谢尔平斯基三角形，如图4-9所示。谢尔平斯基三角形展示了三路递归算法。手动绘制谢尔平斯基三角形的过程十分简单：从一个大三角形开始，通过连接每条边的中点将它分割成四个新的三角形；忽略中间的三角形，利用同样的方法分割其余三个三角形。每一次创建一个新三角形集合，都递归地分割三个三角形。如果笔尖足够细，可以无限地重复这一分割过程。在继续阅读之前，不妨试着亲手绘制谢尔平斯基三角形。

图4-9　谢尔平斯基三角形

既然可以无限地重复分割算法，那么它的基本情况是什么呢？答案是，基本情况根据我们想要的分割次数设定。这个次数有时被称为分形图的“度”。每进行一次递归调用，就将度减1，直到度是0为止。代码清单4-7展示了生成如图4-9所示的谢尔平斯基三角形的代码。

代码清单4-7　绘制谢尔平斯基三角形

1.   from turtle import *
2.
3.   def drawTriangle(points, color, myTurtle):
4.       myTurtle.fillcolor(color)
5.       myTurtle.up()
6.       myTurtle.goto(points[0])
7.       myTurtle.down()
8.       myTurtle.begin_fill()
9.       myTurtle.goto(points[1])
10.      myTurtle.goto(points[2])
11.      myTurtle.goto(points[0])
12.      myTurtle.end_fill()
13.
14.  def getMid(p1, p2):
15.      return ( (p1[0]+p2[0]) /2, (p1[1] + p2[1]) / 2)
16.
17.  def sierpinski(points, degree, myTurtle):
18.      colormap = ['blue', 'red', 'green', 'white', 'yellow',
19.                  'violet', 'orange']
20.      drawTriangle(points, colormap[degree], myTurtle)
21.      if degree > 0:
22.          sierpinski([points[0],
23.                          getMid(points[0], points[1]),
24.                          getMid(points[0], points[2])],
25.                      degree-1, myTurtle)
26.          sierpinski([points[1],
27.                          getMid(points[0], points[1]),
28.                          getMid(points[1], points[2])],
29.                      degree-1, myTurtle)
30.          sierpinski([points[2],
31.                          getMid(points[2], points[1]),
32.                          getMid(points[0], points[2])],
33.                      degree-1, myTurtle)
34.
35.  myTurtle = Turtle()
36.  myWin = myTurtle.getscreen()
37.  myPoints = [(-500, -250), (0, 500), (500, -250)]
38.  sierpinski(myPoints, 5, myTurtle)
39.  myWin.exitonclick()

代码清单4-7中的程序遵循了之前描述的思想。sierpinski首先绘制外部的三角形，接着进行3个递归调用，每一个调用对应生成的一个新三角形。本例再一次使用Python自带的标准turtle模块。在Python解释器中执行help(‘turtle’)，可以详细了解turtle模块中的所有方法。

请根据代码清单4-7思考三角形的绘制顺序。假设三个角的顺序是左下角、顶角、右下角。由于sierpinski的递归调用方式，它会一直在左下角绘制三角形，直到绘制完最小的三角形才会往回绘制剩下的三角形。之后，它会开始绘制顶部的三角形，直到绘制完最小的三角形。最后，它会绘制右下角的三角形，直到全部绘制完成。

函数调用图有助于理解递归算法。由图4-10可知，递归调用总是往左边进行的。在图中，黑线表示正在执行的函数，灰线表示没有被执行的函数。越深入到该图的底部，三角形就越小。函数一次完成一层的绘制；一旦它绘制好底层左边的三角形，就会接着绘制底层中间的三角形，依此类推。

图4-10　谢尔平斯基三角形的函数调用图

sierpinski函数非常依赖于getMid函数，后者接受两个点作为输入，并返回它们的中点。此外，代码清单4-7中有一个函数使用turtle模块的begin_fill和end_fill绘制带颜色的三角形。这意味着谢尔平斯基三角形的每一层都有不同的颜色。

复杂的递归问题

前几节探讨了一些容易用递归解决的问题，以及有助于理解递归的一些有趣的绘图问题。本节将探讨一些用循环难以解决却能用递归轻松解决的问题。最后会探讨一个颇具欺骗性的问题。它看上去可以用递归巧妙地解决，但是实际上并非如此。

汉诺塔
汉诺塔问题由法国数学家爱德华·卢卡斯于1883年提出。他的灵感是一个与印度寺庙有关的传说，相传这座寺庙里的年轻修行者试图解决这个难题。起初，修行者有3根柱子和64个依次叠好的金盘子，下面的盘子大，上面的盘子小。修行者的任务是将64个叠好的盘子从一根柱子移动到另一根柱子，同时有两个重要的限制条件：每次只能移动一个盘子，并且大盘子不能放在小盘子之上。修行者夜以继日地移动盘子（每一秒移动一个盘子），试图完成任务。根据传说，如果他们完成这项任务，整座寺庙将倒塌，整个世界也将消失。

尽管这个传说非常有意思，但是并不需要担心世界会因此而毁灭。要正确移动64个盘子，所需的步数是2^{64}-1=18~446~744~073~709~551~615。根据每秒移动一次的速度，整个过程大约需要584 942 417 355年！显然，这个谜题并不像听上去那么简单。

图4-11展示了一个例子，这是在将所有盘子从第一根柱子移到第三根柱子的过程中的一个中间状态。注意，根据前面说明的规则，每一根柱子上的盘子都是从下往上由大到小依次叠起来的。如果你之前从未求解过这个问题，不妨现在就试一下。不需要精致的盘子和柱子，一堆书或者一叠纸就足够了。

图4-11　汉诺塔问题示例

如何才能递归地解决这个问题呢？它真的可解吗？基本情况是什么？让我们自底向上地来考虑这个问题。假设第一根柱子起初有5个盘子。如果我们知道如何把上面4个盘子移动到第二根柱子上，那么就能轻易地把最底下的盘子移动到第三根柱子上，然后将4个盘子从第二根柱子移动到第三根柱子。但是如果不知道如何移动4个盘子，该怎么办呢？如果我们知道如何把上面3个盘子移动到第三根柱子上，那么就能轻易地把第4个盘子移动到第二根柱子上，然后再把3个盘子从第三根柱子移动到第二根柱子。但是如果不知道如何移动3个盘子，该怎么办呢？移动两个盘子到第二根柱子，然后把第3个盘子移动到第三根柱子，最后把之前的两个盘子移过来，怎么样？但是如果还是不知道如何移动两个盘子，该怎么办呢？你肯定会说，把一个盘子移动到第三根柱子并不难，甚至会说太简单。这看上去就是本例的基本情况。

以下概述如何借助一根中间柱子，将高度为height的一叠盘子从起点柱子移到终点柱子：

(1) 借助终点柱子，将高度为height - 1的一叠盘子移到中间柱子；

(2) 将最后一个盘子移到终点柱子；

(3) 借助起点柱子，将高度为height - 1的一叠盘子从中间柱子移到终点柱子。

只要总是遵守大盘子不能叠在小盘子之上的规则，就可以递归地执行上述步骤，就像最下面的大盘子不存在一样。上述步骤仅缺少对基本情况的判断。最简单的汉诺塔只有一个盘子。在这种情况下，只需将这个盘子移到终点柱子即可，这就是基本情况。此外，上述步骤通过逐渐减小高度height来向基本情况靠近。代码清单4-8展示了解决汉诺塔问题的Python代码。

代码清单4-8　解决汉诺塔问题的Python代码

1.  def moveTower(height, fromPole, toPole, withPole):
2.  if height >= 1:
3.     moveTower(height-1, fromPole, withPole, toPole)
4.     moveDisk(fromPole, toPole)
5.     moveTower(height-1, withPole, toPole, fromPole)

代码清单4-8几乎和用英语描述一样。算法如此简洁的关键在于进行两个递归调用，分别在第3行和第5行。第3行将除了最后一个盘子以外的其他所有盘子从起点柱子移到中间柱子。第4行简单地将最后一个盘子移到终点柱子。第5行将之前的塔从中间柱子移到终点柱子，并将其放置在最大的盘子之上。基本情况是高度为0。此时，不需要做任何事情，因此moveTower函数直接返回。这样处理基本情况时需要记住，从moveTower返回才能调用moveDisk。

moveDisk函数非常简单，如代码清单4-9所示。它所做的就是打印出一条消息，说明将盘子从一根柱子移到另一根柱子。不妨尝试运行moveTower程序，你会发现它是非常高效的解决方案。

代码清单4-9　moveDisk函数

1.  def moveDisk(fp, tp):
2.      print("moving disk from %d to %d\n" % (fp, tp))

看完moveTower和moveDisk的实现代码，你可能会疑惑为什么没有一个数据结构显式地保存柱子的状态。下面是一个提示：若要显式地保存柱子的状态，就需要用到3个Stack对象，一根柱子对应一个栈。Python通过调用栈隐式地提供了我们所需的栈，就像在toStr的例子中一样。

探索迷宫

本节探讨一个与蓬勃发展的机器人领域相关的问题：走出迷宫。如果你有一个Roomba扫地机器人，或许能利用在本节学到的知识对它进行重新编程。我们要解决的问题是帮助小乌龟走出虚拟的迷宫。迷宫问题源自忒修斯大战牛头怪的古希腊神话传说。相传，在迷宫里杀死牛头怪之后，忒修斯用一个线团找到了迷宫的出口。本节假设小乌龟被放置在迷宫里的某个位置，我们要做的是帮助它爬出迷宫，如图4-12所示。

图4-12　帮助小乌龟爬出迷宫

为简单起见，假设迷宫被分成许多格，每一格要么是空的，要么被墙堵上。小乌龟只能沿着空的格子爬行，如果遇到墙，就必须转变方向。它需要如下的系统化过程来找到出路。

从起始位置开始，首先向北移动一格，然后在新的位置再递归地重复本过程。
如果第一步往北行不通，就尝试向南移动一格，然后递归地重复本过程。
如果向南也行不通，就尝试向西移动一格，然后递归地重复本过程。
如果向北、向南和向西都不行，就尝试向东移动一格，然后递归地重复本过程。
如果4个方向都不行，就意味着没有出路。
整个过程看上去非常简单，但是有许多细节需要讨论。假设递归过程的第一步是向北移动一格。根据上述过程，下一步也是向北移动一格。但是，如果北面有墙，必须根据递归过程的第二步向南移动一格。不幸的是，向南移动一格之后回到了起点。如果继续执行该递归过程，就会又向北移动一格，然后又退回来，从而陷入无限循环中。所以，必须通过一个策略来记住到过的地方。本例假设小乌龟一边爬，一边丢面包屑。如果往某个方向走一格之后发现有面包屑，就知道应该立刻退回去，然后尝试递归过程的下一步。查看这个算法的代码时会发现，退回去就是从递归函数调用中返回。

和考察其他递归算法时一样，让我们来看看上述算法的基本情况，其中一些可以根据之前的描述猜到。这个算法需要考虑以下4种基本情况。

(1) 小乌龟遇到了墙。由于格子被墙堵上，因此无法再继续探索。

(2) 小乌龟遇到了已经走过的格子。在这种情况下，我们不希望它继续探索，不然会陷入循环。

(3) 小乌龟找到了出口。

(4) 四个方向都行不通。

为了使程序运行起来，需要通过一种方式表示迷宫。我们使用turtle模块来绘制和探索迷宫，以增加趣味性。迷宫对象提供下列方法，可用于编写搜索算法。

init读入一个代表迷宫的数据文件，初始化迷宫的内部表示，并且找到小乌龟的起始位置。
drawMaze在屏幕上的一个窗口中绘制迷宫。
updatePosition更新迷宫的内部表示，并且修改小乌龟在迷宫中的位置。
isExit检查小乌龟的当前位置是否为迷宫的出口。
除此之外，Maze类还重载了索引运算符[]，以便算法访问任一格的状态。

代码清单4-10展示了搜索函数searchFrom的代码。该函数接受3个参数：迷宫对象、起始行，以及起始列。由于该函数的每一次递归调用在逻辑上都是重新开始搜索的，因此定义成接受3个参数非常重要。

代码清单4-10　迷宫搜索函数searchFrom

1.   def searchFrom(maze, startRow, startColumn):
2.       maze.updatePosition(startRow, startColumn)
3.       # 检查基本情况
4.       # 1. 遇到墙
5.       if maze[startRow][startColumn] == OBSTACLE:
6.           return False
7.       # 2. 遇到已经走过的格子
8.       if maze[startRow][startColumn] == TRIED:
9.           return False
10.      # 3. 找到出口
11.      if maze.isExit(startRow, startColumn):
12.          maze.updatePosition(startRow, startColumn, PART_OF_PATH)
13.          return True
14.      maze.updatePosition(startRow, startColumn, TRIED)
15.
16.      # 否则，依次尝试向4个方向移动
17.      found = searchFrom(maze, startRow-1, startColumn) or \
18.              searchFrom(maze, startRow+1, startColumn) or \
19.              searchFrom(maze, startRow, startColumn-1) or \
20.              searchFrom(maze, startRow, startColumn+1)
21.      if found:
22.          maze.updatePosition(startRow, startColumn, PART_OF_PATH)
23.      else:
24.          maze.updatePosition(startRow, startColumn, DEAD_END)
25.      return found

该函数做的第一件事就是调用updatePosition（第2行）。这样做是为了对算法进行可视化，以便我们看到小乌龟如何在迷宫中寻找出口。接着，该函数检查前3种基本情况：是否遇到了墙（第5行）？是否遇到了已经走过的格子（第8行）？是否找到了出口（第11行）？如果没有一种情况符合，则继续递归搜索。

递归搜索调用了4个searchFrom。很难预测一共会进行多少个递归调用，这是因为它们都是用布尔运算符or连接起来的。如果第一次调用searchFrom后返回True，那么就不必进行后续的调用。可以这样理解：向北移动一格是离开迷宫的路径上的一步。如果向北没有能够走出迷宫，那么就会尝试下一个递归调用，即向南移动。如果向南失败了，就尝试向西，最后向东。如果所有的递归调用都失败了，就说明遇到了死胡同。请下载或自己输入代码，改变4个递归调用的顺序，看看结果如何。

Maze类的方法定义如代码清单4-11~代码清单4-13所示。__init__方法只接受一个参数，即文件名。该文本文件包含迷宫的信息，其中+代表墙，空格代表空的格子，S代表起始位置。图4-13是迷宫数据文件的例子。迷宫的内部表示是一个列表，其元素也是列表。实例变量mazelist的每一行是一个列表，其中每一格包含一个字符。对于图4-13对应的数据文件，其内部表示如下。

[ ['+','+','+','+',...,'+','+','+','+','+','+','+'],
  ['+',' ',' ',' ',...,' ',' ',' ','+',' ',' ',' '],
  ['+',' ','+',' ',...,'+','+',' ','+',' ','+','+'],
  ['+',' ','+',' ',...,' ',' ',' ','+',' ','+','+'],
  ['+','+','+',' ',...,'+','+',' ','+',' ',' ','+'],
  ['+',' ',' ',' ',...,'+','+',' ',' ',' ',' ','+'],
  ['+','+','+','+',...,'+','+','+','+','+',' ','+'],
  ['+',' ',' ',' ',...,'+','+',' ',' ','+',' ','+'],
  ['+',' ','+','+',...,' ',' ','+',' ',' ',' ','+'],
  ['+',' ',' ',' ',...,' ',' ','+',' ','+','+','+'],
  ['+','+','+','+',...,'+','+','+',' ','+','+','+'] ]

图4-13　迷宫数据文件示例

drawMaze方法使用以上内部表示在屏幕上绘制初始的迷宫，如图4-12所示。

updatePosition方法使用相同的内部表示检查小乌龟是否遇到了墙。同时，它会更改内部表示，使用.和-来分别表示小乌龟遇到了走过的格子和死胡同。此外，updatePosition方法还使用辅助函数moveTurtle和dropBreadcrumb来更新屏幕上的信息。

isExit方法检查小乌龟的当前位置是否为出口，条件是小乌龟已经爬到迷宫边缘：第0行、第0列、最后一行或者最后一列。

代码清单4-11　Maze类

1.   class Maze:
2.       def __init__(self, mazeFileName):
3.           rowsInMaze = 0
4.           columnsInMaze = 0
5.           self.mazelist = []
6.           mazeFile = open(mazeFileName, 'r')
7.           rowsInMaze = 0
8.           for line in mazeFile:
9.               rowList = []
10.              col=0
11.              for ch in line[:-1]:
12.                  rowList.append(ch)
13.                  if ch == 'S':
14.                      self.startRow = rowsInMaze
15.                      self.startCol = col
16.                  col = col + 1
17.              rowsInMaze = rowsInMaze + 1
18.              self.mazelist.append(rowList)
19.              columnsInMaze = len(rowList)
20.
21.          self.rowsInMaze = rowsInMaze
22.          self.columnsInMaze = columnsInMaze
23.          self.xTranslate = -columnsInMaze/2
24.          self.yTranslate = rowsInMaze/2
25.          self.t = Turtle(shape='turtle')
26.          setup(width=600, height=600)
27.          setworldcoordinates(-(columnsInMaze-1)/2-.5,
28.                              -(rowsInMaze-1)/2-.5,
29.                              (columnsInMaze-1)/2+.5,
30.                              (rowsInMaze-1)/2+.5)

代码清单4-12　Maze类

1.       def drawMaze(self):
2.           for y in range(self.rowsInMaze):
3.               for x in range(self.columnsInMaze):
4.                   if self.mazelist[y][x] == OBSTACLE:
5.                       self.drawCenteredBox(x+self.xTranslate,
6.                                            -y+self.yTranslate,
7.                                            'tan')
8.           self.t.color('black', 'blue')
9.
10.      def drawCenteredBox(self, x, y, color):
11.          tracer(0)
12.          self.t.up()
13.          self.t.goto(x-.5, y-.5)
14.          self.t.color('black', color)
15.          self.t.setheading(90)
16.          self.t.down()
17.          self.t.begin_fill()
18.          for i in range(4):
19.              self.t.forward(1)
20.              self.t.right(90)
21.          self.t.end_fill()
22.          update()
23.          tracer(1)
24.
25.      def moveTurtle(self, x, y):
26.          self.t.up()
27.          self.t.setheading(self.t.towards(x+self.xTranslate,
28.                                           -y+self.yTranslate))
29.          self.t.goto(x+self.xTranslate, -y+self.yTranslate)
30.
31.      def dropBreadcrumb(self, color):
32.          self.t.dot(color)
33.
34.      def updatePosition(self, row, col, val=None):
35.          if val:
36.              self.mazelist[row][col] = val
37.          self.moveTurtle(col, row)
38.
39.          if val == PART_OF_PATH:
40.              color = 'green'
41.          elif val == OBSTACLE:
42.              color = 'red'
43.          elif val == TRIED:
44.              color = 'black'
45.          elif val == DEAD_END:
46.              color ='red'
47.          else:
48.              color = None
49.
50.          if color:
51.              self.dropBreadcrumb(color)

代码清单4-13　Maze类

1.      def isExit(self, row, col):
2.          return (row == 0 or
3.                  row == self.rowsInMaze-1 or
4.                  col == 0 or
5.                  col == self.columnsInMaze-1)
6.
7.      def __getitem__(self, idx):
8.          return self.mazelist[idx]

动态规划

许多计算机程序被用于优化某些值，例如找到两点之间的最短路径，为一组数据点找到最佳拟合线，或者找到满足一定条件的最小对象集合。计算机科学家采用很多策略来解决这些问题。本书的一个目标就是帮助你了解不同的问题解决策略。在解决优化问题时，一个策略是动态规划。

优化问题的一个经典例子就是在找零时使用最少的硬币。假设某个自动售货机制造商希望在每笔交易中给出最少的硬币。一个顾客使用一张一美元的纸币购买了价值37美分的物品，最少需要找给该顾客多少硬币呢？答案是6枚：25美分的2枚，10美分的1枚，1美分的3枚。该如何计算呢？从面值最大的硬币（25美分）开始，使用尽可能多的硬币，然后尽可能多地使用面值第2大的硬币。这种方法叫作贪婪算法——试图最大程度地解决问题。

对于美国的硬币来说，贪婪算法很有效。不过，假如除了常见的1分、5分、10分和25分，硬币的面值还有21分，那么贪婪算法就没法正确地为找零63分的情况得出最少硬币数。尽管多了21分的面值，贪婪算法仍然会得到6枚硬币的结果，而最优解是3枚面值为21分的硬币。

让我们来考察一种必定能得到最优解的方法。由于本章的主题是递归，因此你可能已经猜到，这是一种递归方法。首先确定基本情况：如果要找的零钱金额与硬币的面值相同，那么只需找1枚硬币即可。

如果要找的零钱金额和硬币的面值不同，则有多种选择：1枚1分的硬币加上找零金额减去1分之后所需的硬币；1枚5分的硬币加上找零金额减去5分之后所需的硬币；1枚10分的硬币加上找零金额减去10分之后所需的硬币；1枚25分的硬币加上找零金额减去25分之后所需的硬币。我们需要从中找到硬币数最少的情况，如下所示。

numCoins = min(1 + numCoins(originalamount - 1),
               1 + numCoins(originalamount - 5),
               1 + numCoins(originalamount - 10),
               1 + numCoins(originalamount - 25))

代码清单4-14实现了上述算法。第3行检查是否为基本情况：尝试使用1枚硬币找零。如果没有一个硬币面值与找零金额相等，就对每一个小于找零金额的硬币面值进行递归调用。第6行使用列表循环来筛选出小于当前找零金额的硬币面值。第7行的递归调用将找零金额减去所选的硬币面值，并将所需的硬币数加1，以表示使用了1枚硬币。

代码清单4-14　找零问题的递归解决方案

1.   def recMC(coinValueList, change):
2.       minCoins = change
3.       if change in coinValueList:
4.           return 1
5.       else:
6.           for i in [c for c in coinValueList if c <= change]:
7.               numCoins = 1 + recMC(coinValueList, change-i)
8.               if numCoins < minCoins:
9.                     minCoins = numCoins
10.      return minCoins
11.
12.  recMC([1, 5, 10, 25], 63)

代码清单4-14的问题是，它的效率非常低。事实上，针对找零金额是63分的情况，它需要进行67 716 925次递归调用才能找到最优解。图4-14有助于理解该算法的严重缺陷。针对找零金额是26分的情况，该算法需要进行377次递归调用，图中仅展示了其中的一小部分。

图4-14　递归调用树

在图4-14中，每一个节点都对应一次对recMC的调用，节点中的数字表示此时正在计算的找零金额，箭头旁的数字表示刚使用的硬币面值。从图中可以发现，采用不同的面值组合，可以到达任一节点。主要的问题是重复计算量太大。举例来说，数字为15的节点出现了3次，每次都会进行52次函数调用。显然，该算法将大量时间和资源浪费在了重复计算已有的结果上。

减少计算量的关键在于记住已有的结果。简单的做法是把最少硬币数的计算结果存储在一张表中，并在计算新的最少硬币数之前，检查结果是否已在表中。如果是，就直接使用结果，而不是重新计算。代码清单4-15实现了添加查询表之后的算法。

代码清单4-15　添加查询表之后的找零算法

1.   def recDC(coinValueList, change, knownResults):
2.       minCoins = change
3.       if change in coinValueList:
4.           knownResults[change] = 1
5.           return 1
6.       elif knownResults[change] > 0:
7.           return knownResults[change]
8.       else:
9.           for i in [c for c in coinValueList if c <= change]:
10.              numCoins = 1 + recDC(coinValueList, change-i,
11.                                   knownResults)
12.              if numCoins < minCoins:
13.                   minCoins = numCoins
14.                   knownResults[change] = minCoins
15.      return minCoins
16.
17.  recDC([1, 5, 10, 25], 63, [0]*63)

注意，第6行会检查查询表中是否已经有某个找零金额对应的最少硬币数。如果没有，就递归地计算并且把得到的最少硬币数结果存在表中。修改后的算法将计算找零63分所需的递归调用数降低到221次！

尽管代码清单4-15实现的算法能得到正确的结果，但是它不太正规。如果查看knownResults表，会发现其中有一些空白的地方。事实上，我们所做的优化并不是动态规划，而是通过记忆化（或者叫作缓存）的方法来优化程序的性能。

真正的动态规划算法会用更系统化的方法来解决问题。在解决找零问题时，动态规划算法会从1分找零开始，然后系统地一直计算到所需的找零金额。这样做可以保证在每一步都已经知道任何小于当前值的找零金额所需的最少硬币数。

让我们来看看如何将找零11分所需的最少硬币数填入查询表，图4-15展示了这个过程。从1分开始，只需找1枚1分的硬币。第2行展示了1分和2分所需的最少硬币数。同理，2分只需找2枚1分的硬币。第5行开始变得有趣起来，此时我们有2个可选方案：要么找5枚1分的硬币，要么找1枚5分的硬币。哪个方案更好呢？查表后发现，4分所需的最少硬币数是4，再加上1枚1分的硬币就得到5分（共需要5枚硬币）；如果直接找1枚5分的硬币，则最少硬币数是1。由于1比5小，因此我们把1存入表中。接着来看11分的情况，我们有3个可选方案，如图4-16所示。

(1) 1枚1分的硬币加上找10分零钱（11–1）最少需要的硬币（1枚）。

(2) 1枚5分的硬币加上找6分零钱（11–5）最少需要的硬币（2枚）。

(3) 1枚10分的硬币加上找1分零钱（11–10）最少需要的硬币（1枚）。

第1个和第3个方案均可得到最优解，即共需要2枚硬币。

图4-15　找零算法所用的查询表

图4-16　找零11分时的3个可选方案

找零问题的动态规划解法如代码清单4-16所示。dpMakeChange接受3个参数：硬币面值列表、找零金额，以及由每一个找零金额所需的最少硬币数构成的列表。当函数运行结束时，minCoins将包含找零金额从0到change的所有最优解。

代码清单4-16　用动态规划算法解决找零问题

1.  def dpMakeChange(coinValueList, change, minCoins):
2.      for cents in range(change+1):
3.          coinCount = cents
4.          for j in [c for c in coinValueList if c <= cents]:
5.              if minCoins[cents-j] + 1 < coinCount:
6.                  coinCount = minCoins[cents -j]+1
7.          minCoins[cents] = coinCount
8.      return minCoins[change]

注意，尽管我们一开始使用递归方法来解决找零问题，但是dpMakeChange并不是递归函数。请记住，能够用递归方法解决问题，并不代表递归方法是最好或最高效的方法。动态规划函数所做的大部分工作是从第4行开始的循环。该循环针对由cents指定的找零金额考虑所有可用的面值。和找零11分的例子一样，我们把最少硬币数记录在minCoins表中。

尽管找零算法在寻找最少硬币数时表现出色，但是由于没有记录所用的硬币，因此它并不能帮助我们进行实际的找零工作。通过记录minCoins表中每一项所加的硬币，可以轻松扩展dpMakeChange，从而记录所用的硬币。如果知道上一次加的硬币，便可以减去其面值，从而找到表中前一项，并通过它知晓之前所加的硬币。代码清单4-17展示了修改后的dpMakeChange算法，以及从表中回溯并打印所用硬币的printCoins函数。

代码清单4-17　修改后的动态规划解法

1.   def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
2.       for cents in range(change+1):
3.           coinCount = cents
4.           newCoin = 1
5.           for j in [c for c in coinValueList if c <= cents]:
6.               if minCoins[cents-j] + 1 < coinCount:
7.                   coinCount = minCoins[cents -j]+1
8.                   newCoin = j
9.           minCoins[cents] = coinCount
10.          coinsUsed[cents] = newCoin
11.      return minCoins[change]
12.
13.  def printCoins(coinsUsed, change):
14.      coin = change
15.      while coin > 0:
16.          thisCoin = coinsUsed[coin]
17.          print(thisCoin)
18.          coin = coin – thisCoin

最后，来看看动态规划算法如何处理硬币面值含21分的情况。前3行创建要使用的硬币列表。接着创建用来存储结果的列表。coinsUsed是一个列表，其中是用于找零的硬币。coinCount是最少硬币数。

>>> cl = [1, 5, 10, 21, 25]
>>> coinsUsed = [0]*64
>>> coinCount = [0]*64
>>> dpMakeChange(cl, 63, coinCount, coinsUsed)
3
>>> printCoins(coinsUsed, 63)
21
21
21
>>> printCoins(coinsUsed, 52)
10
21
21
>>> coinsUsed
[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1,
 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1,
 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10,
 1, 1, 1, 10, 1, 10, 21]

注意，硬币的打印结果直接取自coinsUsed。第一次调用printCoins时，从coinsUsed的位置63处开始，打印出21；然后计算63–21=42，接着查看列表的第42个元素。这一次，又遇到了21。最后，第21个元素也是21。由此，便得到3枚21分的硬币。

小结

本章探讨了递归算法的一些例子。选择这些算法，是为了让你理解递归能高效地解决何种问题。以下是本章的要点。

所有递归算法都必须有基本情况。
递归算法必须改变其状态并向基本情况靠近。
递归算法必须递归地调用自己。
递归在某些情况下可以替代循环。
递归算法往往与问题的形式化表达相对应。
递归并非总是最佳方案。有时，递归算法比其他算法的计算复杂度更高。

关键术语

递归 递归调用 动态规划 分形 基本情况 栈帧

讨论题

画出汉诺塔问题的调用栈（假设起初栈中有3个盘子）。
根据4.4节所描述的规则，在纸上绘制出谢尔平斯基三角形。
采用动态规划算法找零，计算找零33美分所需的最少硬币数（假设除了常见的面值外，还有面值为8美分的硬币）。

编程练习

写一个递归函数来计算数的阶乘。
写一个递归函数来反转列表。
采用下列一个或全部方法修改递归树程序。

修改树枝的粗细程度，使得branchLen越小，线条越细。
修改树枝的颜色，使得当branchLen非常小时，树枝看上去像叶子。
修改小乌龟的转向角度，使得每一个分支的角度都是一定范围内的随机值，例如使角度取值范围是15~45度。运行程序，查看绘制结果。
递归地修改branchLen，使其减去一定范围内的随机值，而不是固定值。
如果实现上述所有改进方法，绘制出的树将十分真实。

找到一种绘制分形山的算法。提示：可以使用三角形。

写一个递归函数来计算斐波那契数列，并对比递归函数与循环函数的性能。
实现汉诺塔问题的一个解决方案，使用3个栈来记录盘子的位置。
使用turtle绘图模块写一个递归程序，画出希尔伯特曲线。
使用turtle绘图模块写一个递归程序，画出科赫雪花。
写一个程序来解决这样一个问题：有2个坛子，其中一个的容量是4加仑，另一个的是3加仑。坛子上都没有刻度线。可以用水泵将它们装满水。如何使4加仑的坛子最后装有2加仑的水？
扩展练习9中的程序，将坛子的容量和较大的坛子中最后的水量作为参数。
写一个程序来解决这样一个问题：3只羚羊和3只狮子准备乘船过河，河边有一艘能容纳2只动物的小船。但是，如果两侧河岸上的狮子数量大于羚羊数量，羚羊就会被吃掉。找到运送办法，使得所有动物都能安全渡河。
利用turtle绘图模块修改汉诺塔程序，将盘子的移动过程可视化。提示：可以创建多只小乌龟，并将它们的形状改为长方形。
帕斯卡三角形由数字组成，其中的数字交错摆放，使得：

a_{nr}=\frac{n!}{r!(n-r)!}

这是计算二项式系数的等式。在帕斯卡三角形中，每个数等于其上方两数之和，如下所示。

    1
  1   1
1   2   1

1 3 3 1
1 4 6 4 1
将行数作为参数，写一个输出帕斯卡三角形的程序。

假设一个计算机科学家兼艺术大盗闯入美术馆。他只能用一个容量为W磅的背包来装盗取的艺术品，并且他对每一件艺术品的价值和重量了如指掌。他会如何写一个动态规划程序来帮助自己最大程度地获利呢？下面的例子可以帮助你思考：假设背包容量是20磅，艺术品为5件。

艺术品 重量 价值
1 2 3
2 3 4
3 4 8
4 5 8
5 9 10
请尝试解决字符串编辑距离问题，它在很多研究领域中非常有用。假设要把单词algorithm转换成alligator。对于每一个字母，可以用5个单位的代价将其从一个单词复制到另一个，也可以用20个单位的代价将其删除或插入。拼写检查程序利用将一个单词转换为另一个的总代价来提供拼写建议。请设计一个动态规划算法，给出任意两个单词之间的最小编辑距离。