四. Recursion

Posted on 2017-02-20 Edited on 2024-11-10 In 《Problem Solving with Algorithms and Data Structures using Python》的学习笔记和课后作业答案

对应本书第四章。

笔记

第四章主讲递归，用了很多有意思的例子（可视化的），所以这章的作业会比较有料。

使用递归的三条件：

问题必须有基础情况;
问题必须可以被分解，直至基础情况；
递归算法必须自己调用自己。

例子：

下面的例子都用到了python的画图模块turtle，但貌似只是个toy，用于教学的，这里有一篇入门教程，随便看看。

from __future__ import print_function
import turtle

# 初始化乌龟对象和屏幕对象
t = turtle.Turtle()
myWin = turtle.Screen()

https://github.com/applenob/algorithm_note/raw/master/res/turtle_init.png

1	t.left(90) # 方向默认是朝右，向左九十度使其向正上方

https://github.com/applenob/algorithm_note/raw/master/res/left_90.png

t.up()和t.down()是指画笔的起落，落下则行动中会留下轨迹，起来则行动不留痕迹；
t.right(degree)和t.left(degree)调整乌龟的方向；
t.forward(distance)和t.backward(distance)使乌龟前进后退；
t.goto(x,y)使乌龟移动到指定点；
t.color(color_str)设置乌龟颜色；
t.fillcolor(color)设置填充颜色，t.begin_fill()在画需要填充颜色的形状前调用，t.end_fill()在画需要填充颜色的形状后调用；
t.setheading()设置乌龟方向：0 - east，90 - north，180 - west，270 - south；
t.pensize()调整画笔尺寸。

1.分形

分形（fractal），就是满足如下条件的图形，无论对图像如何进行放大，它的局部图像和总体图像总是一致的。wikipedia的解释。大自然中的分形有雪花/海岸线等等。

你可以想象如果你是上帝，你在创造海岸线的时候，首先在空中画了一副轮廓，当你想进一步描绘海岸线的细节时，你下降了一些高度，然后按照你刚才的思路，接着画了一模一样的轮廓，如此循环。

上面这个过程，正好符合递归的思路。

下面的代码，画一棵分形的树：

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 draw_tree():
    #t = turtle.Turtle()
    #myWin = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    tree(75,t)
    
draw_tree()

https://github.com/applenob/algorithm_note/raw/master/res/basic_tree.png

接着画一个分形的三角：

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][1])
    myTurtle.goto(points[2][0],points[2][1])
    myTurtle.goto(points[0][0],points[0][1])
    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()
    myTurtle = t
    # myWin = turtle.Screen()
    myPoints = [[-100,-50],[0,100],[100,-50]]
    sierpinski(myPoints,3,myTurtle)

myWin.clearscreen()
main()

https://github.com/applenob/algorithm_note/raw/master/res/triangle.png

2.汉诺塔

汉诺塔规则：

有三根柱子和一些大小不同的盘子。初始状态是所有盘子从大到小一直往上堆积在起始柱上。
每次可以移动一个盘子，到其他两根柱子上，必须保证大的盘子在下面，小的盘子在上面。

最终的目标是把所有盘子从大到小往上堆积在目标柱上。

https://ss3.bdstatic.com/70cFv8Sh_Q1YnxGkpoWK1HF6hhy/it/u=3171323217,1599602218&fm=23&gp=0.jpg

分析：

考虑问题的分解：

如果有n片盘子，那么可以分解成先将n-1片移到中间柱上，再把最大的一片从起始柱移到目标柱上，再把n-1片移到目标柱上。
移动n片盘子和移动n-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)

moveTower(3,"A","B","C")

('moving disk from', 'A', 'to', 'B')
('moving disk from', 'A', 'to', 'C')
('moving disk from', 'B', 'to', 'C')
('moving disk from', 'A', 'to', 'B')
('moving disk from', 'C', 'to', 'A')
('moving disk from', 'C', 'to', 'B')
('moving disk from', 'A', 'to', 'B')

3.迷宫问题

想必这个问题就不用介绍了，就是给定起点和迷宫信息，要找到一条出去的路径。

分析：

如何找到一条可以出去的路呢？

不考虑出去的路的长短的话，我们可以先考虑当前点可能的操作，无非是上下左右移动（能不能移动另说）。

那么我们可以把问题等价于在当前点的所有可能操作+假设这样做了一步之后的整体搜索。

其实说白了就是深度优先搜索。

作者给出了一个turtle实现的案例（都可以做一个游戏了，老外写书真心认真～）

PART_OF_PATH = 'O'
TRIED = '.'
OBSTACLE = '+'
DEAD_END = '-'

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
        # x和y的起点默认在屏幕中心，所以要移到
        self.xTranslate = -columnsInMaze/2
        self.yTranslate = rowsInMaze/2
        # self.t = turtle.Turtle()
        self.t = t
        self.t.shape('turtle')
        # self.wn = turtle.Screen()
        self.wn = myWin
        # 设置窗口的左下角坐标和右上角坐标
        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,'orange')
        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]


def searchFrom(maze, startRow, startColumn):
    # try each of four directions from this point until we find a way out.
    # base Case return values:
    #  1. We have run into an obstacle, return false
    maze.updatePosition(startRow, startColumn)
    if maze[startRow][startColumn] == OBSTACLE :
        return False
    #  2. We have found a square that has already been explored
    if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END:
        return False
    # 3. We have found 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


myWin.clearscreen()
myMaze = Maze('maze2.txt')
myMaze.drawMaze()
myMaze.updatePosition(myMaze.startRow,myMaze.startCol)

searchFrom(myMaze, myMaze.startRow, myMaze.startCol)

True

https://github.com/applenob/algorithm_note/raw/master/res/maze.png

对比动态规划

动态规划（Dynamic Programming）。

递归虽然好用，写起来简单，代码易读，但是依然有很多问题不适合用递归。

比如说动态规划，拿最简单的硬币找钱问题举例子。

比如有三种硬币1,2,5元的，现在有一定数额的总数，请问怎么找前可以使得硬币数最少？
类似的还有背包问题：

比如背包可以装的物品有1，2，5公斤的物品，带来的效益分别是1,3,10元，如何安排物品，使得背包的总效益最大？

如果采用递归去解决这些问题，会产生时间复杂度非常大的问题，为什么呢？比如你要求的是规模是10的问题，你把它缩小成规模是5和5的问题，这两个子问题虽然是相同的问题，但由于递归不会记录子问题的答案，所以会计算两次。

那么我们把每次递归计算的不同规模的问题的答案记录下来呢？

当然可以，这会节省很多时间，但在很多情况下，这不是最高明的算法。

如果采用动态规划，直接从最小规模的问题开始出发，记录所有规模下的问题答案，直到指定的规模，获得结果。

当然，需要具体问题具体分析。

作业

作业原地址

q1

用递归的方法写一个阶乘函数：

def factorial(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return n*factorial(n-1)
    
factorial(4)

q2

用递归的方法逆转一个list：

def reverse(l):
    if len(l) == 1:
        return l
    elif len(l) == 2:
        l[0], l[1] = l[1], l[0]
        return l
    else:
        l[0], l[-1] = l[-1], l[0]
        l[1:-1] = reverse(l[1:-1])
        return l
    
l = [1,2,3,4,5,6]
print reverse(l)

1	[6, 5, 4, 3, 2, 1]

q3

修改作者的分形树：

import random

def myTree(branchLen,t):
    # print branchLen
    if branchLen > 5:
        step = random.randrange(15, 29)
        angle = random.randrange(15, 45)
        t.pensize(max(4, branchLen/step*5))
        if branchLen < 30:
            t.color("green")
        t.forward(branchLen)
        t.right(angle)
        myTree(branchLen-step, t)
        t.left(angle*2)
        myTree(branchLen-step, t)
        t.right(angle)
        t.backward(branchLen)
        t.color("brown")
        
def my_draw_tree():
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("brown")
    myTree(100,t)
    
myWin.clearscreen()    
my_draw_tree()

https://github.com/applenob/algorithm_note/raw/master/res/my_tree.png

画一座分形的山：

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][1])
    myTurtle.goto(points[2][0],points[2][1])
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.end_fill()
    
def drawPlatform(points,color,myTurtle):
    """画一个梯形的平台,其实也可以直接写一个drawPolygon的方法"""
    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][1])
    myTurtle.goto(points[2][0],points[2][1])
    myTurtle.goto(points[3][0],points[3][1])
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.end_fill()

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

def mountain(width,level,color,myTurtle):
    if width > 9:
        drawTriangle([(-width/2.,level),(-width/3.,level+width/3.),(-width/6.,level)],
                     color,myTurtle)
        drawTriangle([(width/6.,level),(width/3.,level+width/3.),(width/2.,level)],
                     color,myTurtle)
        drawPlatform([(-width/3.,level),(-width/6.,level+width/3.),
                      (width/6.,level+width/3.),(width/3.,level)],
                     color,myTurtle)
        mountain(width/3.,level+width/3.,color,myTurtle)
    else:
        drawTriangle([(-width/2.,level),(0.,level+width),(width/2.,level)],
                     color,myTurtle)

def main():
    myTurtle = t
    t.color("white")
    mountain(900,-450,"blue",myTurtle)

myWin.clearscreen()
main()

https://github.com/applenob/algorithm_note/raw/master/res/mountain.png

画风有点像葫芦娃。

q5

用递归的方法解决斐波那契数列：

def genFibonacci(n):
    """递归方法"""
    if n<=2:
        return 1
    else :
        return genFibonacci(n-1)+genFibonacci(n-2)
    
genFibonacci(7)
l = []
for i in range(1, 20):
    l.append(genFibonacci(i))
print l

1	[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

def genFibonacciSequence(n):
    """循环方法"""
    if n<=2:
        return [1]*n
    else:
        l = [1, 1]
        for i in range(2, n):
            l.append(l[i-1]+l[i-2])
    return l
          
print genFibonacciSequence(19)

1	[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

分析：

如果只是生成一个指定序号的斐波那契数，那么两种方法的时间复杂度是一样的。

但是如果生成的是一个序列的话，还是循环方法时间复杂度小，是$O(n)$；递归方法的时间复杂度是$O(n^2)$。

关键还是在于递归方法没有记录计算过的指定序号的斐波那契数的数值。

q6

改进汉诺塔的算法，使用3个栈记录三个柱子的实时情况：

class Tower:
    def __init__(self, name):
        self.name = name
        self.stack = []
        
def get_tower_by_name(name, ts):
    for t in ts:
        if t.name == name:
            return t

def moveTower(height,fromPole, toPole, withPole):
    """宏观上的移动"""
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole, withPole)
        moveTower(height-1, withPole, toPole, fromPole)

def moveDisk(fromPole, toPole, withPole):
    """具体移动一个盘子"""
    print("moving disk from", fromPole.name, "to", toPole.name)
    toPole.stack.append(fromPole.stack.pop())
    print("Tower A: ", get_tower_by_name("A", [fromPole, toPole, withPole]).stack)
    print("Tower B: ", get_tower_by_name("B", [fromPole, toPole, withPole]).stack)
    print("Tower C: ", get_tower_by_name("C", [fromPole, toPole, withPole]).stack)

def main_hanoi(height):
    t_from = Tower("A")
    t_to = Tower("B")
    t_with = Tower("C")
    t_from.stack = range(height, 0, -1)
    moveTower(height, t_from, t_to, t_with)
    
main_hanoi(3)

moving disk from A to B
Tower A:  [3, 2]
Tower B:  [1]
Tower C:  []
moving disk from A to C
Tower A:  [3]
Tower B:  [1]
Tower C:  [2]
moving disk from B to C
Tower A:  [3]
Tower B:  []
Tower C:  [2, 1]
moving disk from A to B
Tower A:  []
Tower B:  [3]
Tower C:  [2, 1]
moving disk from C to A
Tower A:  [1]
Tower B:  [3]
Tower C:  [2]
moving disk from C to B
Tower A:  [1]
Tower B:  [3, 2]
Tower C:  []
moving disk from A to B
Tower A:  []
Tower B:  [3, 2, 1]
Tower C:  []

q7

使用turtle模块，画出Hilbert curve。

Hilbert curve的介绍：wikipedia

思路：

参考这里，将问题分解成画“三笔凸包”和连接线。

def draw_hilbert(x0, y0, xis, yis, xjs, yjs, n):
    """
    x0 和 y0是左下角的坐标；
    xis 和 yis是右下角坐标（凸包的终点方向）；
    xjs 和 yjs是左上角坐标（下一笔方向）；
    上述坐标皆是相对于缺口朝下的方向。
    """
    if n <= 0:
        t.goto(x0+(xis+yis)/2, y0+(xjs+yjs)/2);
    else:
        draw_hilbert(x0, y0, yis/2, xis/2, yjs/2, xjs/2, n-1)  # 画左下角分区 
        draw_hilbert(x0+xis/2, y0+xjs/2 ,xis/2, yis/2, xjs/2, yjs/2, n-1)  # 画左上角分区 
        draw_hilbert(x0+xis/2+yis/2, y0+xjs/2+yjs/2, xis/2, yis/2, xjs/2, yjs/2,n-1)  # 画右上角分区 
        draw_hilbert(x0+xis/2+yis, y0+xjs/2+yjs, -yis/2, -xis/2, -yjs/2, -xjs/2, n-1)  # 画右下角分区 

myWin.clearscreen()
t.up()
t.goto(0, 0)
t.down()
draw_hilbert(0., 0., 300., 0., 0., 300., 1)

q8

使用turtle模块，画出Koch snowflake。

介绍参考wiki-pedia。

思路：

首先将任务分成三个相同的三部分，即三角形的三条边，不管每条边如何复杂化，都是相同的操作。
对于每条边，宏观上的操作如下，（在一根直线上长出一个角）：

def koch(length, order):
    if order > 0:
        for turn in [0, 60, -120, 60]:
            t.left(turn)
            koch(length/3., order-1)            
    else:
        t.forward(length)


def draw_koch(length, order):
    for i in range(3):
        koch(length, order)
        t.right(120)
        
myWin.clearscreen()
t.pensize(2)
t.speed(10)
t.goto(0, 0)
t.down()
draw_koch(100., 3)

目录

笔记

1.分形

2.汉诺塔

3.迷宫问题

对比动态规划

作业

q1

q2

q3

q5

q6

q7

q8