递归的方法需要不断地练习，后期会有算法不断的运用到其思想。将大问题分解为相同的小问题，直至结束。
代码语言：python代码运行次数：0复制# 谢尔宾斯基三角
import turtle
t = turtle.Turtle()
points = {'left': (-200, -100), 'top': (0, 200), 'right': (200, -100)}
def sierpinski(degree, points):
colormap = ['blue', 'red', 'green', 'white', 'yellow', 'orange']
drawtriangle(points, colormap[degree])
if degree > 0:
sierpinski(degree - 1,
{'left': points['left'],
'top': getmid(points['left'], points['top']),
'right': getmid(points['left'], points['right'])})
sierpinski(degree - 1,
{'left': getmid(points['left'], points['top']),
'top': points['top'],
'right': getmid(points['top'], points['right'])})
sierpinski(degree - 1,
{'left': getmid(points['left'], points['right']),
'top': getmid(points['top'], points['right']),
'right': points['right']})
def drawtriangle(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)
sierpinski(5, points)
turtle.done()# 汉诺塔移动，思想：若最大盘片不移动，相当于不存在，所以只需移动较小一层级，最终对应于只移动一只。
def move_tower(height, frompole, withpole, topole):
if height >= 1:
move_tower(height-1, frompole, topole, withpole)
move_disk(height, frompole, topole)
move_tower(height-1, withpole, frompole, topole)
def move_disk(disk, frompole, topole):
print(f"Moving disk[{disk}] from {frompole} to {topole}") # 学习这种用法
move_tower(4, '#1', '#2', '#3')# 自动售货机的找零问题，贪心算法，但是会做很多次重复的算法。
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))# 自动售货机找零问题的升级算法，记录其他情况下的最优算法，进行一次查表操作。
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))
