数据结构Python版--递归_python数据结构递归树

递归

递归定义

解决问题的一种方法，将问题不断的分成更小的子问题，直到子问题可以用普通的方法解决。递归会使用一个不停调用自己的函数。

# 使用循环求和函数
def listsum(numList):
    theSume = 0
    for i in numList:
        theSume = theSume + i
    return theSume

# 使用递归
def listsum(numList):
    # 退出语句
    if len(numList) == 1:
        return numList[0]
    else:
        # [1:]使用第一个元素之后的内容
        return numList[0] + listsum(numList[1:])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

递归三原则：
1.递归算法必须有基本情况（使算法停止递归的条件）
2.递归算法必须改变其状态并向基本情况靠近
3.递归算法必须递归的调用自己
递归的逻辑并不是循环，而是将问题分解成更小、更容易解决的子问题。

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

将一个整数转换成以2~16为基数的字符串。
算法包括三个部分：
1.将原来的整数分成一系列仅有单数位的数
2.通过查表将单数位的数转换成字符串
3.连接得到的字符串，从而形成结果

# 进制转换
def toStr(n,base):
    converString = "0123456789ABCDEF"
    if n < base:
        return converString[n]
    else:
        return toStr(n//base,base) + converString[n%base]
print(toStr(8,2))

# 使用栈
class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items) - 1]

    def size(self):
        return len(self.items)

rStack = Stack()

def toStr(n,base):
    converString = "0123456789ABCDEF"
    if n < base:
        rStack.push(converString[n])
    else:
        rStack.push(converString[n%base])
        toStr(n//base,base)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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

递归可视化

使用递归来绘制有趣团的例子。

'''
绘制小乌龟
使用turtle模块递归的绘制螺旋线
函数的基本情况是：要画的线的长度降为0，如果线的长度大于0，就让小乌龟向前移动len个单位距离，然后向右旋转90度，

'''
from turtle import *
# 创建小乌龟对象
myTurtle = Turtle()
# 创建绘制团的窗口
myWin = myTurtle.getscreen()

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

drawSpiral(myTurtle,100)
# 进入等待模式，直到用户在窗口内再次点击之后
# 程序清理并退出
myWin.exitonclick()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

绘制一颗分形树，分形的定义是不论方法多少倍来观察分形图，总是有相同的基本形状。即使是一根小细支也右和一整棵树一样的形状和特征。把树定义为树干，其上长着一颗向左生长和向右生长的子树，可以将树的递归定义运用到它的左右子树上。

# 绘制分形树
def tree(branchLen,t):
    if branchLen >5:
        t.forward(branchLen)
        # 向右转向20
        t.right(20)
        tree(branchLen-15,t)
        # 向左转向20，同时抵消之前向右转向的20
        t.left(40)
        tree(branchLen-10,t)
        t.right(20)
        t.backward(branchLen)

t = Turtle()
myWin = t.getscreen()

t.left(90)
t.up()
t.backward(300)
t.down()
t.color('green')
tree(110,t)
myWin.exitonclick()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

树上的每一个分支点都对应一次递归调用，而且程序先绘制右子树，并一路到其最短的嫩枝，接着程序一路返回到树干，以此绘制右子树。然后绘制左子树，左子树自己的右子树被玩外脑画好之后才会绘制最左端的嫩枝。

谢尔平斯基三角形

展示了三路递归算法。从一个大三角形开始，通过连接每条边的中点将它分割成四个新的三角形；忽略中间的三角形，利用同样的方法分割其余三个三角形。每一次创建一个新的三角形集合，都递归的分割三个三角形。这个递归算法的基本情况根据我们想要的分割次数设定，这个次数有时会被称为分形图的”度“。每进行一次递归调用，就要将度减1，直到度是0为止。

# 绘制谢尔平斯基三角形
def drawTriangle(points,color,myTurtle):
    myTurtle.fillcolor(color)
    myTurtle.up()
    myTurtle.goto(points[0])
    myTurtle.down()
    myTurtle.begin_fill()
    myTurtle.goto(points[1])
    myTurtle.goto(points[2])
    myTurtle.goto(points[0])
    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)


myTurtle = Turtle()
myWin = myTurtle.getscreen()
myPoints = [(-500,-250),(0,500),(500,-250)]
sierpinski(myPoints,5,myTurtle)
myWin.exitonclick()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

汉诺塔

问题分析：假设第一根柱子起初有5个盘子，如果我们知道如何将4个盘子移动到第二根柱子上，就能轻易的把最底下的盘子移动到第三根柱子上，然后将4个盘子从第二根柱子移动到第三根柱子。但是如果不知道如何移动4个盘子，考虑移动上面三个盘子，一次类推，不知道如何移动两个盘子，把一个盘子移动到第三根柱子上。
借助一根中间柱子，将高度为height的一叠盘子从起点柱子移动到终点柱子：
1.借助终点柱子，将高度为height-1的一叠盘子移动到中间柱子；
2.将最后一个盘子移动到终点柱子
3.借助起点柱子，将高度为height-1的一叠盘子从中间柱子移动到终点柱子。

# 汉诺塔
# fromPole起始柱 toPole工具柱 withPole工具柱子
def moveTower(height,fromPole,toPole,withPole):
    if height >= 1:
        # B为工具柱
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        # A为工具柱
        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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

探索迷宫

需要解决的问题是帮助小乌龟走出虚拟迷宫：
将迷宫分为许多格，每一格要么是空的，要么被堵上。小乌龟只能沿着空的格子爬行，如果遇到墙，就必须转变方向。
1.从起始位置开始，首先向北移动一格，然后在新的位置再递归的重复本过程。
2.如果第一步往北行不通，就尝试向南移动一格，然后递归的重复本过程。
3.如果向南也不行，就尝试向西移动一格，然后递归的重复本过程。
4.如果向西不行就舱室向东移动一格，然后递归的重复本过程。
5.如果4个方向都不行就意味着没有出路。
此过程看着简单，为了保证不陷入无限的循环中，必须通过一个策略来记住到过的地方。假设小乌龟一边爬一遍丢面包屑，如果往某个方向走一格之后发现有面包屑，就直到应该立刻退回，然后尝试递归过程的下一步。
该算法需要考虑以下4种情况：
1.小乌龟遇到了墙，由于格子被墙堵上，因此无法再继续探索。
2.小乌龟遇到了已经走过的路。
3.小乌龟找到了出口。
4.四个方向都行不通。

'''
使用turtle模块来绘制和探索迷宫
__init__读入一个代表迷宫的数据文件，初始化迷宫的内部表示，找到小乌龟的起始位置
drawMaze绘制迷宫
updatePosition更新迷宫的内部表示，修改小乌龟在迷宫中的位置
isExit检查小乌龟的当前位置是否为迷宫的出口
'''
import 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
        # 用于计算方块的长宽
        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(5)

        # 如果遇到墙就画成一个方形
        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')

    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


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

searchFrom(myMaze, myMaze.startRow, myMaze.startCol)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

动态规划

经典案例是在找零时使用最少的硬币。基本情况是：如果要找的零钱和硬币的面值相同，就只需要找一枚硬币即可。如果要找的零钱金额和硬币的面值不同，则有多种选择：一枚一分的硬币加上找零金额减去一分之后所需的硬币；一枚5分的硬币加上找零金额减去5分之后所需的硬币；一枚10分的硬币加上找零金额减去10分之后所需硬币，一枚25分的硬币加上找零金额减去25分之后所需的硬币。

# 找零算法递归求解
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,8,10],16))
print(recMC([1,5,10,25],26))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

每一个节点都对应一次的recMC的调用，节点中的数字表示此时正在计算的找零金额，上述算法的问题是重复计算量太大，数字节点为15的出现了3次，该算法将大量时间和资源浪费在了重复计算已有结果上。
减少计算量的关键是记住已有的结果，简单的做法是把最少的硬币数的计算结构存储在一张表中，并在计算新的最少硬币数之前，检查是否已经在表中，如果是就直接使用结果，而不是重新计算。

# 添加查询之后的找零算法
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

算法会检查查询表中是否已经有某个找零金额对应的最少硬币数，如果没有就递归的计算并且把得到的最少硬币数结果存在表中。如果查看knowResults表就会发现其中有一些空白的地方，我们所做的优化不是动态规划，而是通过记忆化的方法来优化程序的性能。
真正的动态规划算法会用更系统化的方法来解决问题，在解决找零问题的时候，动态规划算法会从1分找零开始，系统的一直计算到所需的找零金额。这样做可以保证在每一步都已经知道任何小于当前值的找零金额所需的最少硬币数。

def dpMakeChange(coinValueList,change,minConis):
    for cents in range(change+1):
        coinCount = cents
        for j in [c for c in coinValueList if c <= cents]:
         # 在这一步中也进行了一次比较 所以可以保证是最小值
            if minConis[cents-j] + 1 <coinCount:
                coinCount = minConis[cents - j]+1
        minConis[cents] = coinCount
    return minConis[change]
1
2
3
4
5
6
7
8
9

但是此算法没有记录所用的硬币所以不能帮助我们进行实际的找零工作。

# 利用动态规划来解决找零问题
def dpMakeChange(coinValueList,change,minConis,coinsUsed):
    for cents in range(change+1):
        coinCount = cents
        newCoin = 1
        for j in [c for c in coinValueList if c <= cents]:
            if minConis[cents-j] + 1 <coinCount:
                coinCount = minConis[cents - j]+1
                newCoin = j
        minConis[cents] = coinCount
        coinsUsed[cents] = newCoin
    return minConis[change]

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

c1 = [1,2,5,7,10]
coinsUsed = [0]*15
coinCount = [0]*15
dpMakeChange(c1,14,coinCount,coinsUsed)
printCoins(coinsUsed,14)
print("1",dpMakeChange(c1,14,coinCount,coinsUsed))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26