递归三原则

所有的递归算法都要遵守三个重要的原则：

  1. 递归算法必须有基本情况；
  2. 递归算法必须改变其状态并向基本情况靠近；
  3. 递归算法必须递归地调用自己。

计算一列数之和

循环求和函数：

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

递归求和函数：

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

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

基本情况：数字小于 10。

整个算法包含三个组成部分：

  1. 将原来的整数分成一系列仅有单数位的数；
  2. 通过查表将单数位的数转换成字符串；
  3. 连接得到的字符串，从而形成结果。
def toStr(n,base):
   convertString = "0123456789ABCDEF"
   if n < base:
      return convertString[n]
   else:
      return toStr(n//base,base) + convertString[n%base]

栈帧：实现递归

假设不拼接递归调用 toStr 的结果和 convertString 的查找结果，而是在进行递归调用之前把字符串压入栈中。

from pythonds.basic import Stack

rStack = Stack()

def toStr(n,base):
    convertString = "0123456789ABCDEF"
    if n < base:
        rStack.push(convertString[n])
    else:
        rStack.push(convertString[n % base])
        toStr(n // base, base)

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

递归可视化

尽管能用递归轻松解决的问题。但是，要想象递归的样子或者将递归过程可视化仍然十分困难。

我们将使用 Python 的 turtle 模块来绘制图案。Python 的各个版本都提供 turtle 模块，它用起来非常简便。

使用 turtle 模块递归地绘制螺旋线

import turtle

myTurtle = turtle.Turtle()
myWin = turtle.Screen()

def drawSpiral(myTurtle, lineLen):
    if lineLen > 0:
        myTurtle.forward(lineLen)
        myTurtle.right(90)
        drawSpiral(myTurtle,lineLen-5)

drawSpiral(myTurtle,100)
myWin.exitonclick()

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

用 turtle 模块绘制分形树

import turtle

def tree(branchLen,t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-15,t)
        t.right(20)
        t.backward(branchLen)

def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    tree(75,t)
    myWin.exitonclick()

main()

用 turtle 模块绘制谢尔平斯基三角形

import turtle

def drawTriangle(points,color,myTurtle):
    myTurtle.fillcolor(color)
    myTurtle.up()
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.down()
    myTurtle.begin_fill()
    myTurtle.goto(points[1][0],points[1][2])
    myTurtle.goto(points[2][0],points[2][3])
    myTurtle.goto(points[0][0],points[0][4])
    myTurtle.end_fill()

def getMid(p1,p2):
    return ( (p1[0]+p2[0]) / 2, (p1[1] + p2[1]) / 2)

def sierpinski(points,degree,myTurtle):
    colormap = ['blue','red','green','white','yellow',
                'violet','orange']
    drawTriangle(points,colormap[degree],myTurtle)
    if degree > 0:
        sierpinski([points[0],
                        getMid(points[0], points[1]),
                        getMid(points[0], points[2])],
                   degree-1, myTurtle)
        sierpinski([points[1],
                        getMid(points[0], points[1]),
                        getMid(points[1], points[2])],
                   degree-1, myTurtle)
        sierpinski([points[2],
                        getMid(points[2], points[1]),
                        getMid(points[0], points[2])],
                   degree-1, myTurtle)

def main():
   myTurtle = turtle.Turtle()
   myWin = turtle.Screen()
   myPoints = [[-100,-50],[0,100],[100,-50]]
   sierpinski(myPoints,3,myTurtle)
   myWin.exitonclick()

main()

sierpinski 首先绘制外部的三角形，接着进行 3 个递归调用，每一个调用对应生成的一个新三角形。

复杂的递归问题

汉诺塔

python_recursion_fig_1.png

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

  1. 借助终点柱子，将高度为 height − 1 的一叠盘子移到中间柱子；
  2. 将最后一个盘子移到终点柱子；
  3. 借助起点柱子，将高度为 height − 1 的一叠盘子从中间柱子移到终点柱子。
def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

探索迷宫

python_recursion_fig_2.png

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

  • 从起始位置开始，首先向北移动一格，然后在新的位置再递归地重复本过程。
  • 如果第一步往北行不通，就尝试向南移动一格，然后递归地重复本过程。
  • 如果向南也行不通，就尝试向西移动一格，然后递归地重复本过程。
  • 如果向北、向南和向西都不行，就尝试向东移动一格，然后递归地重复本过程。
  • 如果 4 个方向都不行，就意味着没有出路。

假设递归过程的第一步是向北移动一格。根据上述过程，下一步也是向北移动一格。但是，如果北面有墙，必须根据递归过程的第二步向南移动一格。不幸的是，向南移动一格之后回到了起点。如果继续执行该递归过程，就会又向北移动一格，然后又退回来，从而陷入无限循环中。

所以，必须通过一个策略来记住到过的地方。本例假设小乌龟一边爬，一边丢面包屑。如果往某个方向走一格之后发现有面包屑，就知道应该立刻退回去，然后尝试递归过程的下一步。查看这个算法的代码时会发现，退回去就是从递归函数调用中返回。

这个算法需要考虑以下 4 种基本情况：

  1. 小乌龟遇到了墙。由于格子被墙堵上，因此无法再继续探索。
  2. 小乌龟遇到了已经走过的格子。在这种情况下，我们不希望它继续探索，不然会陷入循环。
  3. 小乌龟找到了出口。
  4. 四个方向都行不通。

我们使用 turtle 模块来绘制和探索迷宫，以增加趣味性。迷宫对象提供下列方法，可用于编写搜索算法：

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

迷宫搜索函数 searchFrom：

def searchFrom(maze, startRow, startColumn):
    maze.updatePosition(startRow, startColumn)
    #  Check for base cases:
    #  1. We have run into an obstacle, return false
    if maze[startRow][startColumn] == OBSTACLE :
        return False
    #  2. We have found a square that has already been explored
    if maze[startRow][startColumn] == TRIED:
        return False
    # 3. Success, an outside edge not occupied by an obstacle
    if maze.isExit(startRow,startColumn):
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
        return True
    maze.updatePosition(startRow, startColumn, TRIED)

    # Otherwise, use logical short circuiting to try each
    # direction in turn (if needed)
    found = searchFrom(maze, startRow-1, startColumn) or \
            searchFrom(maze, startRow+1, startColumn) or \
            searchFrom(maze, startRow, startColumn-1) or \
            searchFrom(maze, startRow, startColumn+1)
    if found:
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
    else:
        maze.updatePosition(startRow, startColumn, DEAD_END)
    return found

Maze 类的方法：

class Maze:
    def __init__(self,mazeFileName):
        rowsInMaze = 0
        columnsInMaze = 0
        self.mazelist = []
        mazeFile = open(mazeFileName,'r')
        rowsInMaze = 0
        for line in mazeFile:
            rowList = []
            col = 0
            for ch in line[:-1]:
                rowList.append(ch)
                if ch == 'S':
                    self.startRow = rowsInMaze
                    self.startCol = col
                col = col + 1
            rowsInMaze = rowsInMaze + 1
            self.mazelist.append(rowList)
            columnsInMaze = len(rowList)

        self.rowsInMaze = rowsInMaze
        self.columnsInMaze = columnsInMaze
        self.xTranslate = -columnsInMaze/2
        self.yTranslate = rowsInMaze/2
        self.t = turtle.Turtle()
        self.t.shape('turtle')
        self.wn = turtle.Screen()
        self.wn.setworldcoordinates(-(columnsInMaze-1)/2-.5,
                            -(rowsInMaze-1)/2-.5,
                            (columnsInMaze-1)/2+.5,
                            (rowsInMaze-1)/2+.5)

    def drawMaze(self):
        self.t.speed(10)
        self.wn.tracer(0)
        for y in range(self.rowsInMaze):
            for x in range(self.columnsInMaze):
                if self.mazelist[y][x] == OBSTACLE:
                    self.drawCenteredBox(x+self.xTranslate,
                                     -y+self.yTranslate,
                                     'tan')
        self.t.color('black')
        self.t.fillcolor('blue')
        self.wn.update()
        self.wn.tracer(1)

    def drawCenteredBox(self,x,y,color):
        self.t.up()
        self.t.goto(x-.5,y-.5)
        self.t.color(color)
        self.t.fillcolor(color)
        self.t.setheading(90)
        self.t.down()
        self.t.begin_fill()
        for i in range(4):
            self.t.forward(1)
            self.t.right(90)
        self.t.end_fill()

    def moveTurtle(self,x,y):
        self.t.up()
        self.t.setheading(self.t.towards(x+self.xTranslate,
                                     -y+self.yTranslate))
        self.t.goto(x+self.xTranslate,-y+self.yTranslate)

    def dropBreadcrumb(self,color):
        self.t.dot(10,color)

    def updatePosition(self,row,col,val=None):
        if val:
            self.mazelist[row][col] = val
        self.moveTurtle(col,row)

        if val == PART_OF_PATH:
            color = 'green'
        elif val == OBSTACLE:
            color = 'red'
        elif val == TRIED:
            color = 'black'
        elif val == DEAD_END:
            color = 'red'
        else:
            color = None

        if color:
            self.dropBreadcrumb(color)

    def isExit(self,row,col):
        return (row == 0 or
                row == self.rowsInMaze-1 or
                col == 0 or
                col == self.columnsInMaze-1 )

    def __getitem__(self,idx):
        return self.mazelist[idx]

Maze 类的方法定义：

  • __init__ 方法只接受一个参数，即文件名。该文本文件包含迷宫的信息，其中 + 代表墙，空格代表空的格子，S 代表起始位置。
  • drawMaze 方法使用以上内部表示在屏幕上绘制初始的迷宫。
  • updatePosition 方法使用相同的内部表示检查小乌龟是否遇到了墙。同时，它会更改内部表示，使用 . 和 - 来分别表示小乌龟遇到了走过的格子和死胡同。此外，updatePosition 方法还使用辅助函数 moveTurtle 和 dropBreadcrumb 来更新屏幕上的信息。
  • isExit 方法检查小乌龟的当前位置是否为出口，条件是小乌龟已经爬到迷宫边缘。

动态规划（找零问题）

许多计算机程序被用于优化某些值，例如找到两点之间的最短路径，为一组数据点找到最佳拟合线，或者找到满足一定条件的最小对象集合。计算机科学家采用很多策略来解决这些问题。

优化问题的一个经典例子就是在找零时使用最少的硬币。假设某个自动售货机制造商希望在每笔交易中给出最少的硬币。

找零问题的递归解决方案

基本情况：如果要找的零钱金额与硬币的面值相同，那么只需找 1枚硬币即可。

如果要找的零钱金额和硬币的面值不同，则有多种选择：

  • 1 枚 1 分的硬币加上找零金额减去 1 分之后所需的硬币；
  • 1 枚 5 分的硬币加上找零金额减去 5 分之后所需的硬币；
  • 1 枚 10 分的硬币加上找零金额减去 10 分之后所需的硬币；
  • 1 枚 25 分的硬币加上找零金额减去 25 分之后所需的硬币。

我们需要从中找到硬币数最少的情况，如下所示：

$$
\begin{split} numCoins =
min
\begin{cases}
1 + numCoins(original amount - 1) \\
1 + numCoins(original amount - 5) \\
1 + numCoins(original amount - 10) \\
1 + numCoins(original amount - 25)
\end{cases}
\label{eqn_change}\end{split}
$$

def recMC(coinValueList,change):
   minCoins = change
   if change in coinValueList:
     return 1
   else:
      for i in [c for c in coinValueList if c <= change]:
         numCoins = 1 + recMC(coinValueList,change-i)
         if numCoins < minCoins:
            minCoins = numCoins
   return minCoins

print(recMC([1,5,10,25],63))

上述代码问题是，它的效率非常低。针对找零金额是 26 分的情况，该算法需要进行 377 次递归调用，下图中仅展示了其中的一小部分。

python_recursion_fig_3.png

从图中可以发现，采用不同的面值组合，可以到达任一节点。主要的问题是重复计算量太大。举例来说，数字为 15 的节点出现了 3 次，每次都会进行 52 次函数调用。显然，该算法将大量时间和资源浪费在了重复计算已有的结果上。

添加查询表之后的找零算法

减少计算量的关键在于记住已有的结果。简单的做法是把最少硬币数的计算结果存储在一张表中，并在计算新的最少硬币数之前，检查结果是否已在表中。如果是，就直接使用结果，而不是重新计算。

 def recDC(coinValueList,change,knownResults):
    minCoins = change
    if change in coinValueList:
       knownResults[change] = 1
       return 1
    elif knownResults[change] > 0:
       return knownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change]:
          numCoins = 1 + recDC(coinValueList, change-i,
                               knownResults)
          if numCoins < minCoins:
             minCoins = numCoins
             knownResults[change] = minCoins
    return minCoins

 print(recDC([1,5,10,25],63,[0]*64))

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

用动态规划算法解决找零问题

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

python_recursion_fig_4.png

上图展示了如何将找零 11 分的过程。从 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 存入表中。

python_recursion_fig_5.png

接着来看 11 分的情况，我们有 3 个可选方案：

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

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

def dpMakeChange(coinValueList,change,minCoins):
   for cents in range(change+1):
      coinCount = cents
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
      minCoins[cents] = coinCount
   return minCoins[change]

dpMakeChange 接受 3 个参数：硬币面值列表、找零金额，以及由每一个找零金额所需的最少硬币数构成的列表。当函数运行结束时，minCoins 将包含找零金额从 0 到 change 的所有最优解。

注意：尽管我们一开始使用递归方法来解决找零问题，但是 dpMakeChange 并不是递归函数。

修改后的动态规划解法

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

def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
   for cents in range(change+1):
      coinCount = cents
      newCoin = 1
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
               newCoin = j
      minCoins[cents] = coinCount
      coinsUsed[cents] = newCoin
   return minCoins[change]

def printCoins(coinsUsed,change):
   coin = change
   while coin > 0:
      thisCoin = coinsUsed[coin]
      print(thisCoin)
      coin = coin - thisCoin

递归并非总是最佳方案。有时，递归算法比其他算法的计算复杂度更高。