Python基础之递归函数的应用
文章目录
- 递归的定义
- 循环和递归的区别
- 递归函数的实例
- 科赫雪花
- 雪花晶片
- 汉诺塔
递归的定义
函数定义中调用函数自身的方式称为递归。就像一个人站在装满镜子房间中，看到的影响就是递归的结果。
数学上有个经典的递归例子叫阶乘：
n！=n(n-1)(n-2)......(1)
另一种表达阶乘的方式
1 n=0 n！= n(n-1)！ otherwise
这个定义说明0的阶乘 按定义是1，其他数字的阶乘定义为这个数字乘以比这个数字小1数的阶乘。递归不是循环，因为每次递归都会计算比它更小数的阶乘，直到0！。0！是已知的值，被称为递归的基例，当递归到底了，就需要一个能直接算出值的表达式。
阶乘的例子揭示了递归的两个关键特征。
（1）存在一个或多个基例，基例不需要再次递归，它是确定的表达式。
（2）所有递归链要以一个或多个基例结尾。
根据用户输入的整数n，计算并输出n的阶乘：
def fact(n):
if n==0:
return 1 #当n=0，fact()函数不再使用递归函数，返回值1
else:
return n*fact(n-1) #当n != 0，通过递归返回n与n-1阶乘的乘积
num=int(input("请输入一个整数："))
print(fact(abs(num)))
--------------------------------------------------------------
输出结果：
请输入一个整数：5
120
递归遵循函数的语义，每次调用都会引起新函数的开始，表示它有本地变量值的副本，包括函数的参数。例如5！的递归调用，每次函数调用时，函数参数的副本会临时存储，递归中各函数再运算自己的参数，相互没有影响，当基例结束运算并返回值时，各函数逐层结束运算，想调用者返回计算结果。
循环和递归的区别1、利用循环绘制大小不同的五角星。
import turtle
def draw_wjx(size):
i=1
while i<5:
turtle.fd(size)
turtle.rt(144)
i +=1
def main():
turtle.penup()
turtle.backward(200)
turtle.pendown()
turtle.pensize(3)
turtle.pencolor("red")
j=200
while j<=300:
draw_wjx(j)
j +=50
turtle.done()
main()
2、利用递归绘制不同大小的五角星
import turtle
def draw_wjx2(size):
i=1
while i<5:
turtle.fd(size)
turtle.rt(144)
i +=1
size+=50
if size <=300:
draw_wjx2(size) #递归
def main():
turtle.penup()
turtle.backward(200)
turtle.pendown()
turtle.pensize(3)
turtle.pencolor("red")
draw_wjx2(200)
turtle.done()
main()
总结：循环和递归的区别
循环由已知推未知，不断向后。
递归由未知寻找已知，不断向前，递归的实质是出入栈，效率较低。
科赫雪花绘制方法：
（1）正整数n代表科赫雪花的阶数，表示生成科赫雪花过程的操作次数。科赫雪花初始化阶数为0，表示一个长度为L的直线。
（2）将直线L等分成3段，每段长度为L/3。
（3）中间一段用边长为L/3的等边三角形的两个边代替，这样得到1阶的科赫雪花曲线。
（4）重复前面（2）（3）的操作。
import turtle
def draw_koch(size,n):
if n == 1:
turtle.fd(size) # 1阶的科赫雪花曲线就是一条直线
else:
for angle in [0,60,-120,60]: # turtle在“尖”的四条线上改变的角度，分别为0°，60°，-120°，60°
turtle.left(angle) # 对应上边四个角度，一共需要转4次弯，画出本阶的四条线，
draw_koch(size/3,n-1)# 每个角度下的一个边，对应低一阶的科赫雪花曲线的“尖”；
def main():
turtle.setup(800,400)
turtle.speed(0)
turtle.penup()
turtle.goto(-300,-50)
turtle.pendown()
turtle.pensize(2)
draw_koch(200,4)
turtle.hideturtle() #将光标隐藏
main()
输出结果
前面的代码只是完成一个由“尖”组成的“边”，并不是完整的科赫雪花曲线。
完整的科赫雪花曲线由3个“边”组成，转动120度，使得科赫雪花曲线能围城一个三角形，形成最终的科赫雪花效果。
import turtle
def draw_koch(size,n):
'''科赫曲线--一个由“尖”组成的“边”'''
if n == 1:
turtle.fd(size)
else:
for angle in [0,60,-120,60]:
turtle.left(angle)
draw_koch(size/3,n-1)
def draw_into():
'''画笔初始化'''
turtle.setup(600,600)
turtle.speed(0)
turtle.penup()
turtle.goto(-200,100)
turtle.pendown()
turtle.pensize(2)
def main(size,n):
'''完整的n阶科赫雪花曲线'''
draw_into()
draw_koch(size,n) # 完整的科赫雪花曲线由3个“边”组成。
turtle.right(120)#转动120度，使得科赫曲线能围城一个三角形，形成最终的科赫雪花
draw_koch(size,n)
turtle.right(120)
draw_koch(size,n)
turtle.hideturtle()
main(400,5)
输出的结果
根据科赫雪花绘制的方法绘制雪花晶片
（1）当阶数为1时，画出一条直线L。
（2）当阶数大于1时，先将直线二等分，即L/2，左转60度，画出长度L/3的直线，再沿着直线移动-L/3长度回到二等分的位置，再左转-120度，画出长度L/3的直线，再沿着直线移动-L/3长度回到二等分的位置，最后左转60度，再进行二等分。
import turtle
def draw_snow(size,n):
if n == 1:
turtle.fd(size) #当n=1阶时，绘制直线
else:
draw_snow(size/2,n-1) #当n>1阶时,将直线进行二等分
for angle in [60,-120]:
turtle.left(angle)# 左转60度，画出长度L/3的直线，再沿着直线移动-L/3长度回到二等分的位置，
draw_snow(size/3,n-1)
turtle.fd(-size/3)
turtle.left(60) #最后左转60度
draw_snow(size/2,n-1) #再进行二等分
def draw_into():
'''画笔初始化'''
turtle.setup(600,600)
turtle.speed(0)
turtle.penup()
turtle.goto(0,0)
turtle.pendown()
turtle.pensize(2)
turtle.left(90)
def main(size,n):
draw_into()
draw_snow(size,n)
turtle.hideturtle()
main(200,5)
输出结果：
绘制6片晶片形成完整的晶片雪花效果
import turtle
def draw_snow(size,n):
'''绘制晶片'''
if n == 1:
turtle.fd(size)
else:
draw_snow(size/2,n-1)
for angle in [60,-120]:
turtle.left(angle)
draw_snow(size/3,n-1)
turtle.fd(-size/3)
turtle.left(60)
draw_snow(size/2,n-1)
def draw_into():
'''画笔初始化'''
turtle.setup(600,600)
turtle.speed(0)
turtle.penup()
turtle.goto(0,0)
turtle.pendown()
turtle.pensize(2)
turtle.left(90) #将画笔朝上
def main(size,n):
draw_into()
i=1
while i <=6: #绘制6片晶片
turtle.goto(0,0) #每次回到原点位置绘制
draw_snow(size,n)
turtle.right(60) #每片晶片的角度60度，绘制6次，形成完整的雪花晶片
turtle.hideturtle() #每片绘制完将光标隐藏
turtle.done() #结束绘制
main(200,5) #直线长度为200, 5阶的雪花晶片
输出结果
汉诺塔源于真实的故事，在世界某个地方有个很虔诚的宗教组织，期中僧侣维护着一项神圣任务：保持宇宙时间。在时间的最开始，僧侣在平台上竖立了3个垂直杆，在最左侧上有64个不同半径的金色同心圆盘，直径较大的圆盘堆放在下方，形成金字塔样的整体外观，僧侣们的任务是将有所圆盘从最左侧杆子移动到最右侧杆子，这个宗教认为当僧侣们完成任务的时候，万事万物将会化为乌有，宇宙结束。为了保持神圣的顺序，僧侣们移动圆盘需要尊从特定的规则，一次只能移动一个盘子，盘子只能在3个杆子之间移动，更大的盘子不能放在更小的盘子上面。
实现把 A 的 n 个盘子移动到 C（盘子编号是 [1, n] ），要求每次只能移动1个盘子，大盘子只能放在小盘子下面。
1、1个盘子移动时
直接从A移到C上
2、2个盘子移动时
此时借助中间B杆子，盘子1移到B杆子，盘子2移到C杆子，再将B杆子中的盘子1移到C杆子上。即A->B，A->C，B->C。
3、3个盘子移动时
借助中间B杆子，盘子1从A杆移到C杆子，盘子2从A杆移到B杆，再将盘子1从C杆移到B杆中，将盘子3从A杆移到C杆，将盘子1从B杆移到A杆，将盘子2从B杆移到C杆，最后将盘子1从A杆移到C杆。即A->C，A->B，C->B，A->C (此时最大的盘子已经移动到C。接下来剩下的要从B经过A（新的过度柱）移动到C，即B->A，B->C，A->C。
4、思路
（1）当 n == 1时，直接将盘子从 A 移动到C
（2）当 n > 1时，可以拆分成3大步骤
①将 n– 1 个盘子从 A 移动到B，可以利用递归调用
②将编号n最大的盘子从A移到C
③ 将编号n-1的盘子从B移到C，可以利用递归调用
def hanoi(n,A,B,C): #定义汉诺塔函数,参数n是圆盘数，A、B、C是3根柱
if n==1: #判断圆盘数，如果等于1，递归条件
print("第{}个盘子从{}---->{}".format(n,A,C)) # 直接将A柱上的圆盘移动到C柱上
else: #否则，进行递归移动
hanoi(n-1,A,C,B) #递归将A柱最上方的n-1个盘子落在B柱
print("第{}个盘子从{}---->{}".format(n,A,C)) # 将最大的盘子移到C柱上
hanoi(n-1,B,A,C) #递归将B柱上的n-1个盘子，移到C柱上
hanoi(3,'A','B','C') #调用函数
第1个盘子从A---->C
第2个盘子从A---->B
第1个盘子从C---->B
第3个盘子从A---->C
第1个盘子从B---->A
第2个盘子从B---->C
第1个盘子从A---->C
