数据结构与算法（11）—递归
- 递归问题
将问题分解为更小的相同问题——>用非常简单直接地方式解决——>调用自身。
例子：数列求和问题
1 def listsum(numList): 2 if len(numList) ==1: 3 return numList[0] 4 else: 5 return numList[0] + listsum(numList[1:]) #送进去listsum的是一个list 6 print(listsum([1,2,3,4,5,9]))
- 递归三定律
1.递归算法必须有一个基本结束条件
2.递归算法必须能改变状态向基本结束条件演进（减小问题规模）
3.递归算法必须调用自身
- 递归应用
1.整数任意进制转换
1 def toStr(n,base): 2 \'\'\' 3 :param n: 要转换的十进制整数 4 :param base: 转换成的n进制 5 :return: 转换结果 6 \'\'\' 7 convertString = \'0123456789ABCDEF\' 8 if n < base: 9 return convertString[n] 10 else: 11 return toStr(n//base, base) + convertString[n%base] 12 print(toStr(76989,16))
注：这里需要理解下递归的调用时依赖栈的。如toStr函数，当每次调用递归函数，toStr(n)入栈，但此时还没返回，最先入栈的在栈底，最后入栈的在栈顶。 最先返回的是toStr(1)，此时调用顺序和返回顺序是相反的。
即：每次调用，压入栈的现场数据为栈帧，当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回。
2.递归作图
1 import turtle 2 #画箭头 3 t = turtle.Turtle() 4 t.forward(100) 5 turtle.done()
1 #画正方形 2 for i in range(4): 3 t.forward(100) 4 t.right(90) 5 turtle.done()
1 #画五角星 2 t = turtle.Turtle() 3 t.pencolor(\'red\') 4 t.pensize(3) 5 for i in range(5): 6 t.forward(100) #长度 7 t.right(144) #右转角144° 8 t.hideturtle() 9 turtle.done()
1 t = turtle.Turtle() 2 def drawSpiral(t,lineLen): 3 \'\'\' 4 画螺旋，从外向内画 5 \'\'\' 6 if lineLen > 0: 7 t.forward(lineLen) 8 t.right(90)#右转90° 9 drawSpiral(t, lineLen - 5) 10 drawSpiral(t, 100) 11 turtle.done()
3.画分形树
1 def tree(branch_len): 2 if branch_len > 5:#树干太短不画 3 t.forward(branch_len) #画树干 4 t.right(20) #右倾斜20° 5 tree(branch_len - 15) #画右小树，树干减15 6 t.left(40) #向左倾斜20° 7 tree(branch_len - 15) #画左小树，树干减15 8 t.right(20) #向右回20°，回正 9 t.backward(branch_len) #海龟退回原位置 10 t = turtle.Turtle() 11 t.left(90) 12 t.penup() 13 t.backward(100) 14 t.pendown() 15 t.pencolor(\'green\') 16 t.pensize(2) 17 tree(75) 18 t.hideturtle() 19 turtle.done
注：分形树对于我来说挺难理解的，全靠debug帮我理清逻辑，首先一定要记住递归函数栈的进栈顺序和函数调用顺序，这里很关键。
4.谢尔宾斯基三角形
就长这个样子，自己领会吧。它是由3个尺寸减半的谢尔宾斯基三角形按照品字形状叠拼起来的。
画谢尔宾斯基三角形代码：
1 import turtle 2 3 def sierpinski(degree, points): 4 colormap= [\'blue\',\'red\',\'green\',\'white\',\'yellow\',\'orange\'] 5 drawTriangle(points,colormap[degree]) 6 if degree >0: 7 #画左边小三角形 8 sierpinski(degree-1,{\'left\':points[\'left\'], #左边坐标不变 9 \'top\':getMid(points[\'left\'],points[\'top\']), #顶部坐标为左边和顶部的中点 10 \'right\':getMid(points[\'left\'],points[\'right\'])}) #右边坐标为原来左边和右边的中点 11 # 画中间小三角形 12 sierpinski(degree - 1, {\'left\':getMid(points[\'left\'], points[\'top\']), 13 \'top\':points[\'top\'], 14 \'right\':getMid(points[\'top\'], points[\'right\'])}) 15 # 画右边小三角形 16 sierpinski(degree - 1, {\'left\': getMid(points[\'left\'], points[\'right\']), 17 \'top\': getMid(points[\'top\'], points[\'right\']), 18 \'right\': points[\'right\']}) 19 # 绘制填充等边三角形 20 def drawTriangle(points,color): 21 t.fillcolor(color) 22 t.penup() 23 t.goto(points[\'top\']) 24 t.pendown() 25 t.begin_fill() 26 t.goto(points[\'left\']) 27 t.goto(points[\'right\']) 28 t.goto(points[\'top\']) 29 t.end_fill() 30 31 def getMid(p1,p2): 32 return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2) #((x1+x2)/2,(y1+y2)/2) 33 34 t = turtle.Turtle() 35 36 points = {\'left\':(-200,-100),#外轮廓三个顶点坐标 37 \'top\':(0,200), 38 \'right\':(200,-100)} 39 sierpinski(5,points) #画5阶三角形 40 turtle.done()
效果图：
5.汉诺塔问题
问题表述是这样的：（懒得码字，直接截图啦）
如果说要把64个盘片搬完，需要2^64 -1=18 446 744 073 709 551 615次。
首先先看下3个大中小盘，3根柱子，初始在1号柱，挪动方法：首先将小盘挪到3号柱子，中盘挪到2号柱，再将在3号的小盘挪到2号中盘上，再将1号大盘挪到3号柱，再将2号小盘挪到1号柱，再将2号重盘挪到3号柱，最后将1号小盘挪到3号柱，则完成。
对于有4个盘子，3根柱子问题可以考虑先将上面3个挪到2号柱，再将第4个挪到3号柱。
对于有5个盘子，3根柱子问题则考虑现将上面4个挪到2号柱，再将第5个挪到3号柱。
可以看到，这其实就是个递归问题。
将盘片从开始柱，经由中间柱，移动到目标柱的解决思路：
(1)将上层N-1个盘子的从开始柱(fromPole)，经由目标柱(toPole)，移动到中间柱(withPole)；
(2)将第N个(最大的那个)，从开始柱(fromPole)，移动到目标柱(toPole)；
(3)将放置在中间柱N-1个盘子的盘子塔，从中间柱(withPole)，经由开始柱(fromPole)，移动到目标柱(toPole)。
(4)递归
看下代码：
1 def moveTower(height,fromPole,withPole,toPole): 2 \'\'\' 3 :param height: 汉诺塔高度 4 :param fromPole: 起始移动所在柱子 5 :param withPole:中间柱子 6 :param toPole:目的柱子 7 :return: 8 \'\'\' 9 if height >=1: 10 moveTower(height-1,fromPole,toPole,withPole) 11 moveDisk(height,fromPole,toPole) 12 moveTower(height-1,withPole,fromPole,toPole) 13 #直接从fromPole到toPole 14 def moveDisk(disk,fromPole,toPole): 15 print(f\'moving disk[{disk}] from {fromPole} to {toPole}\') 16 17 moveTower(5,\'#1\',\'#2\',\'#3\')
运行结果：
moving disk[1] from #1 to #3 moving disk[2] from #1 to #2 moving disk[1] from #3 to #2 moving disk[3] from #1 to #3 moving disk[1] from #2 to #1 moving disk[2] from #2 to #3 moving disk[1] from #1 to #3 moving disk[4] from #1 to #2 moving disk[1] from #3 to #2 moving disk[2] from #3 to #1 moving disk[1] from #2 to #1 moving disk[3] from #3 to #2 moving disk[1] from #1 to #3 moving disk[2] from #1 to #2 moving disk[1] from #3 to #2 moving disk[5] from #1 to #3 moving disk[1] from #2 to #1 moving disk[2] from #2 to #3 moving disk[1] from #1 to #3 moving disk[3] from #2 to #1 moving disk[1] from #3 to #2 moving disk[2] from #3 to #1 moving disk[1] from #2 to #1 moving disk[4] from #2 to #3 moving disk[1] from #1 to #3 moving disk[2] from #1 to #2 moving disk[1] from #3 to #2 moving disk[3] from #1 to #3 moving disk[1] from #2 to #1 moving disk[2] from #2 to #3 moving disk[1] from #1 to #3 Process finished with exit code 0
6.递归可视化，探索迷宫
迷宫的数据结构：用矩阵方式来实现。
1 class Maze: 2 def __init__(self,mazeFileName): 3 columnsInmaze = 0 4 self.mazelist = [] 5 mazeFile = open(mazeFileName,\'r\') 6 rowsInMaze = 0 7 for line in mazeFile: 8 rowList = [] 9 col = 0 10 for ch in line[:-1]: 11 rowList.append(ch) 12 if ch == \'s\': #海龟投放点S 13 self.startRow = rowsInMaze 14 self.startCo = col 15 col = col+1 16 rowsInMaze = rowsInMaze + 1 17 self.mazelist.append(rowList) 18 columnsInmaze = len(rowList) 19 maze = Maze(\'maze.txt\')
探索思路为：将海龟从原位置向北移东一步，以新位置递归调用探索迷宫寻找出口，并边走边洒面包屑，如果向北找不到出口，则海龟从原始位置向南移动，更新迷宫位置，如向南找不到出口，则从原始位置向西移动一步，更新迷宫位置，如向西找不到出口，则从原始位置向东移动一步，如果都找不到，则迷宫没有出口，但如果一旦发现某前进方格上有面包屑，则立即从递归调用返回上一级。
递归结束的基本条件为：
海龟碰到墙壁方格，递归调用结束，返回失败；
海龟碰到面包屑方格，递归调用结束，返回失败；
海龟碰到出口方格，递归调用结束，返回成功；
海龟在四个方向上探索都失败，递归调用结束，返回失败。
探索迷宫的核心代码：
1 def searchFrom(selfmaze,startRow,startColumn): 2 #1.碰到墙壁，返回失败 3 maze.updatePosition(startRow,startColumn) 4 if maze[startRow][startColumn] == OBSTACLE: 5 return False 6 #2.碰到面包屑，或者死胡同，返回失败 7 if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END 8 return False 9 #3.碰到了出口，返回成功 10 if maze.isExis(startRow,startColumn): 11 maze.updatePosition(startRow,startColumn,TRIED) 12 #4.洒面包屑，继续探索 13 maze.uodataPosition(startRow,startColumn,TRIED) 14 15 #向北南东4个方向依次探索，or操作符具有短路效应 16 found = searchFrom(maze, startRow-1, startColumn) or\ 17 searchFrom(maze, startRow+1, startColumn) or\ 18 searchFrom(maze, startRow, startColumn-1) or\ 19 searchFrom(maze, startRow, startColumn+1) 20 if found: 21 maze.updatePosition(startRow,startColumn,PART_OF_PATH) 22 else: 23 maze.updatePosition(startRow,startColumn,DEAD_END) 24 return found
版权声明：本文为yeshengCqupt原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。