【数据结构与算法Python版学习笔记】递归(Recursion)——定义及应用：分形树、谢尔宾斯基三角、汉诺塔、迷宫

2022-10-31 11:07:23

定义

递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到可以被很简单直接解决。
通常为了达到分解问题的效果，递归过程中要引入一个调用自身的函数。

举例

数列求和

def listsum(numlist):

    if len(numlist) == 1:

        return numlist[0]

    else:

        return numlist[0]+listsum(numlist[1:])

if __name__ == "__main__":

    print(listsum([1, 3, 5, 7, 9]))

递归三大定律

就像阿西莫夫（l.Asimov）的“机器人三定律”一样，递归算法也要遵循三条重要的定律：

递归算法必须有个基本结束条件
递归算法必须改变自己的状态并向基本结束条件演进
递归算法必须递归地调用自身

应用

整数转换为任意进制

def toStr(n, base):

    convertString = "0123456789ABCDEF"

    if n < base:

        return convertString[n] # 最小规模

    else:

        return toStr(n//base,base)+convertString[n % base] # 减小规模，调用自身

if __name__ == "__main__":

    print(toStr(10,2))

    print(toStr(255,16))

递归调用的实现

当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈
- 每次调用，压入栈的现场数据成为栈帧
- 当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回
易碰到错误：RecursionError
- 递归的层数太多，系统调用栈容量有限
- 递归深度限制
  - 检查程序中是否忘记设置基本结束条件，导致无限递归
  - 或者向基本结束条件演进太慢，导致递归层数太多，调用栈溢出
- 在python内置的sys模块可以获取和调整最大递归深度
```
import sys

sys.getrecursionlimit()#默认1000

sys.setrecursionlimit(3000)#自定义设置

sys.getrecursionlimit()
```

递归可视化

海归作图 turtle module

爬行
- forward(n)
- backward(n)
转向
- left(a)
- right(a)
抬笔放笔
- penup()
- pendown()
笔属性
- pensize(s)
- pencolor(c)

# 递归

def listsum(numlist):

    if len(numlist) == 1:

        return numlist[0]

    else:

        return numlist[0]+listsum(numlist[1:])

def toStr(n, base):

    convertString = "0123456789ABCDEF"

    if n < base:

        return convertString[n]

    else:

        return toStr(n//base,base)+convertString[n % base]

import turtle

def draw_forward():

    """前向示例"""

    t=turtle.Turtle()

    # 作图开始

    t.forward(100) #指挥海归作图

    # 作图结束

    turtle.done()

def draw_square():

    """绘制正方形"""

    t=turtle.Turtle()

    for i in range (4):

        t.forward(100)

        t.right(90)

    turtle.done()

def draw_pentagram():

    """绘制五角星"""

    t=turtle.Turtle()

    for i in range (5):

        t.forward(100)

        t.right(144)

    turtle.done()

def drawSpiral(t,linelen):

    """绘制螺旋"""

    if linelen>0:

        t.forward(linelen)

        t.right(90)

        drawSpiral(t,linelen-10)

if __name__ == "__main__":

    #draw_forward()

    #draw_square()

    #draw_pentagram()

    t=turtle.Turtle()

    drawSpiral(t,200)

    turtle.done()

分形树：自相似递归图形

import turtle

def tree(t,branch_len):

    if branch_len>5:

        t.forward(branch_len)

        t.right(20)

        tree(t,branch_len-15)

        t.left(40)

        tree(t,branch_len-15)

        t.right(20)

        t.backward(branch_len)

if __name__ == "__main__":

    t=turtle.Turtle()

    t.left(90)

    t.penup()

    t.backward(100)

    t.pendown()

    t.pencolor("green")

    t.pensize(2)

    tree(t,75)

    t.hideturtle()

    turtle.done()

谢尔宾斯基三角

作图思路

degree=n
- 三角形是由3个degree=n-1的三角形按照品字形拼叠而成
- 这个3个degree=n-1的三角形边长均为degree=n的三角形的一半(规模减小)
degree=0
- 等边三角形，这是递归的基本结束条件

代码

import turtle

def sierpinski(t, degree, points):

    """谢尔宾斯基三角"""

    colormap = ['blue', 'red', 'green', 'white', 'yellow', 'orange']

    drawTriangle(t, points, colormap[degree])

    if degree > 0:

        # 左边三角形

        sierpinski(t, degree-1,

                   {

                       'left': points['left'],

                       'top': getMid(points['left'], points['top']),

                       'right': getMid(points['left'], points['right'])

                   }

                   )

        # 顶部三角形

        sierpinski(t, degree-1,

                   {

                       'left': getMid(points['left'], points['top']),

                       'top': points['top'],

                       'right': getMid(points['top'], points['right'])

                   }

                   )

        # 右边三角形

        sierpinski(t, degree-1,

                   {

                       'left': getMid(points['left'], points['right']),

                       'top': getMid(points['top'], points['right']),

                       'right': points['right']

                   }

                   )

def drawTriangle(t, points, color):

    t.fillcolor(color)

    t.penup()

    t.goto(points['top'])

    t.pendown()

    t.begin_fill()

    t.goto(points['left'])

    t.goto(points['right'])

    t.goto(points['top'])

    t.end_fill()

def getMid(p1, p2):

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

if __name__ == "__main__":

    t = turtle.Turtle()

    points = dict(

        left=(-200, -100),

        top=(0, 200),

        right=(200, -100)

    )

    sierpinski(t, 5, points)

    turtle.done()

汉诺塔

描述

汉诺塔问题是法国数学家爱德华·卢卡斯于1883年发现的。他受到一个关于印度教寺庙的传说的启发，故事中这一问题交由年轻僧侣们解决。最开始，僧侣们得到三根杆子， 64个金圆盘堆叠在其中一根上, 每个圆盘比其下的小一点。僧侣们的任务是将64个圆盘从一根杆上转移到另一根杆上，但有两项重要的限制,一是他们一次只能移动一个圆盘,一是不能将大圆盘放在小圆盘之上。僧侣们日以继夜地工作，每秒移动一个圆盘。传说中，当工作完成之时寺庙就会崩塌, 世界则将不复存在。
传说很有趣，但也不用为世界末日将要到来而担心。毫无差错地完成这项工作需要264-1=18,446,774,073,709,551,615次移动。如果每秒移动一次则需要584,942,417,335（五千亿）年!显然实际上会更长

递归思路

将盘片塔从开始柱，经由中间柱，移动到目标柱：
1. 首先将上层N-1个盘片的盘片塔，从开始柱，经由目标柱，移动到中间柱
2. 然后将第N个（最大）盘片，从开始柱，移动到目标柱
3. 最后将放置在中间柱的N-1个盘片的盘片塔，经由开始柱，移动到目标柱
基本结束条件，即最小规模问题：一个盘片的移动问题

代码实现

def moveTower(height,fromPole,withPole,toPole):

    if height>=1:

        moveTower(height-1,fromPole,toPole,withPole)

        moveDisk(height,fromPole,toPole)

        moveTower(height-1,withPole,fromPole,toPole)

def moveDisk(disk,fromPole,toPole):

    print(f"Moving disk[{disk}] from {fromPole} to {toPole}")

if __name__ == "__main__":

    moveTower(3,"#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

探索迷宫

原文

古希腊迷宫
- 克里特岛米诺斯王
- 牛头人身怪物米诺陶洛斯
圆明园万花阵

算法思路

步骤
- 在初始位置尝试向北走一步，以此为开始递归程序。
- 北面走不通的情况下则向南尝试，其后开始递归。
- 南面走不通的情况下则向西尝试，其后开始递归。
- 如果北面、南面、西面都走不通，则从东面开始并递归程序
- 如果四个方向都走不出，则被困在迷宫中，以失败告终
四种基本情况需要考虑:

1、海龟碰到“墙壁”，方格被占用无法通行。

2、海龟发现表示此方格已访问过，为避免陷入循环不在此位置继续寻找。

3、海龟碰到位于边缘的通道，即找到迷宫出口。

4、海龟在四个方向上探索都失败。
递归归纳：
- 海龟碰到“墙壁”方格，递归调用结束，返回失败
- 海龟碰到“面包屑”方格，表示此方格已访问过，递归调用结束，返回失败
- 海龟碰到“出口”方格，即“位于边缘的通道”方格，递归调用结束，返回成功！
- 海龟在四个方向上的探索都失败，递归调用结束，返回失败

代码实现

代码

import turtle

PART_OF_PATH = 'O'

TRIED = '.'

OBSTACLE = '+'

DEAD_END = '-'

class Maze:

    def __init__(self):

        self.mazelist = [

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

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

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

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

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

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

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

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

            ['+', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ','+', ' ', '+', ' ', 'S', '+', ' ', '+', ' ', ' ', '+'],

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

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

        ]

        self.startRow=8

        self.startCol=15

        self.rowsInMaze =len(self.mazelist)

        self.columnsInMaze =len(self.mazelist[0])

        self.xTranslate=-self.columnsInMaze/2

        self.yTranslate=self.rowsInMaze/2

        self.t = turtle.Turtle()

        self.t.shape('turtle')

        self.wn = turtle.Screen()

        self.wn.setworldcoordinates(-(self.columnsInMaze-1)/2-.5,

                                    -(self.rowsInMaze-1)/2-.5,

                                    (self.columnsInMaze-1)/2+.5,

                                    (self.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):

    # 1.碰到墙壁，返回失败

    maze.updatePosition(startRow, startColumn)

    if maze[startRow][startColumn] == OBSTACLE :

        return False

    # 2. 碰到面包屑，或者死胡同，返回失败

    if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END:

        return False

    # 3. 碰到出口，返回成功

    if maze.isExit(startRow,startColumn):

        maze.updatePosition(startRow, startColumn, PART_OF_PATH)

        return True

    # 4.洒下面包屑，继续探索

    maze.updatePosition(startRow, startColumn, TRIED)

    # 向北南西东4个方向依次探索，or操作符具有短路效应

    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

if __name__ == "__main__":

    myMaze = Maze()

    myMaze.drawMaze()

    myMaze.updatePosition(myMaze.startRow,myMaze.startCol)

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

    turtle.done()

码农公寓

定义

举例

递归三大定律

应用

整数转换为任意进制

递归调用的实现

递归可视化

海归作图 turtle module

分形树：自相似递归图形

谢尔宾斯基三角

作图思路

代码

汉诺塔

描述

递归思路

代码实现

探索迷宫

算法思路

代码实现

相关文章