Python之递归

秒速五厘米 2022-02-20 02:13 286阅读 0赞

**递归：**  
递归就是自己调用自己，无限循环下去，直到遇到终止条件（必须有，否则程序会崩溃）。

**递归与循环：**  
递归更容易理解，也更容易出现bug；循环性能更高。

使用递归要有一个停止递归的条件，否则会一直循环下去，最后溢出。 所以每个递归函数要有两个部分：基线条件和递归条件。

**基线条件：**  
指的是函数不再调用自己的条件，从而避免形成无限循环。  
涉及list的递归，基线条件通常是list为空或只包含一个元素。

**递归条件：**  
指函数开始调用自己的条件。

**示例1：递减函数**

def countDown(i):
    	print(i)
    	if i <= 0: 				#基线条件
    		return
    	else: 					#递归条件
    		countDown(i - 1)
    
    countDown(10)

**结果为：**

10
    9
    8
    7
    6
    5
    4
    3
    2
    1
    0

**示例2：n!阶乘函数**

def fact(i):
    	if i == 1:
    		return 1
    	else:
    		return i * fact(i - 1)
    
    print(fact(5))

**结果为：**

120

**示例3：求和函数**

def sum2(arr):
    	if len(arr) == 0:
    		return 0
    	else:
    		return arr[0] + sum2(arr[1:])
    
    arr = [1, 3, 5, 7, 9]
    print(sum2(arr))

**结果为：**

**示例4：计数函数**

def count2(arr):
    	if len(arr) == 0:
    		return 0
    	else:
    		return 1 + count2(arr[:-1])
    
    arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
    print(count2(arr))

**结果为：**

**示例5：找最大数**

def max_num(arr):
    	if len(arr) == 1:
    		return arr[0]
    	else:
    		if arr[0] > arr[1]:	#获取值相等或小的索引
    			i = 1
    		else:
    			i = 0
    		arr.pop(i) 			#删除上面获取的相等或小的值，保留相对大的值
    		return max_num(arr)
    
    arr = [1, 1, 5, 3, 19, 5, 7, 9, 11, 13, 15, 17]
    print(max_num(arr))

**结果为：**

**示例6：10进制转换成2-16进制**

def ten_to_n(num, base):
    	digits = "0123456789ABCDEF"	#用于表示(2-16进制中)超过9的余数，如需转换成更多进制数，可在后面接着加字母，最多转换成36进制数（10个数字+26个字母）
    	shang = num // base 		#获取商
    	yu = num % base 			#获取余
    	if shang == 0: 				#基线条件
    		return digits[yu]
    	else:
    		return ten_to_n(shang, base) + digits[yu]
    
    print(ten_to_n(233, 8))

**结果为：**

351

**示例7：用海龟画一个递归螺线**

import turtle
    
    def drawSpiral(myTurtle, lineLen):
    	if lineLen > 0:						#若线的长度>0，则
    		myTurtle.forward(lineLen)		#前进lineLen个单位
    		myTurtle.right(90)				#然后右转90度
    		drawSpiral(myTurtle, lineLen-5)	#线的长度缩短5并继续循环
    
    myTurtle = turtle.Turtle()				#创建一个海龟对象
    myWin = turtle.Screen() 				#创建一个能在里面作图的窗口
    drawSpiral(myTurtle, 100) 				#100为线的初始长度
    myWin.exitonclick()						#设置待机状态，若点击窗口，则页面清空并退出程序

**结果为：**  
![在这里插入图片描述][20190412115707918.png_pic_center]  
**示例8：递归分形树**

def tree(t, branchLen):
    	if branchLen > 5:				#若树干的长度>5，则
    		t.forward(branchLen)		#前进branchLen个单位
    		t.right(20) 				#然后右转20度
    		tree(t, branchLen-15)		#右枝继续递归
    		t.left(40)					#然后左转40度，其中20度用于抵消上面的右转20度
    		tree(t, branchLen-10)		#左枝继续递归
    		t.right(20)					#然后右转20度，即0度，原路返回
    		t.backward(branchLen)		#后退branchLen个单位，原路返回
    
    def main():
    	t = turtle.Turtle()				#创建一个海龟对象
    	myWin = turtle.Screen()			#创建一个能在里面作图的窗口
    	t.left(90) 						#左转90度
    	t.up()							#画笔抬起
    	t.backward(100)					#后退100
    	t.down()						#画笔落下
    	t.color("green")				#画笔为绿色
    	tree(t, 100)					#100为树干的初始长度
    	myWin.exitonclick()				#设置待机状态，若点击窗口，则页面清空并退出程序
    
    main()

**结果为：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4ODgyMzI3_size_16_color_FFFFFF_t_70_pic_center]  
**示例9：谢尔宾斯基三角形**

def sierpinski(points, degree, myTurtle):
    	colormap = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'purple']	#三角形填充色
    	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)		#画右下角三角形并填充颜色
    
    # 以左下——>上——>右下——>左下的顺序画三角形并填充颜色
    def drawTriangle(points, color, myTurtle):
        myTurtle.fillcolor(color)													#填充颜色
        myTurtle.begin_fill()														#开始给三角形填充颜色
        myTurtle.up()																#画笔抬起
        myTurtle.goto(points[0][0], points[0][1])									#画笔前往三角形左下角的顶点
        myTurtle.down()																#画笔落下
        myTurtle.goto(points[1][0], points[1][1])									#画笔前往三角形上顶点
        myTurtle.goto(points[2][0], points[2][1])									#画笔前往三角形右下角的顶点
        myTurtle.goto(points[0][0], points[0][1])									#画笔前往三角形左下角的顶点
        myTurtle.end_fill()															#结束给三角形填充颜色
    
    # p1、p2为两个端点，返回这两个端点组成线段的中点坐标
    def getMid(p1, p2):
        return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
    
    def main2():
    	myTurtle = turtle.Turtle()													#创建一个海龟对象
    	myWin = turtle.Screen()														#创建一个能在里面作图的窗口
    	myPoints = [[-100, -50], [0, 100], [100, -50]]								#最外层三角形的顶点坐标
    	sierpinski(myPoints, 4, myTurtle)											#4为画三角形的层级数
    	myWin.exitonclick()															#设置待机状态，若点击窗口，则页面清空并退出程序
    
    main2()

**结果为：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4ODgyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]  
**示例10：河内塔问题**

def moveDisk(num, fromPole, toPole, withPole):
    	if num > 0: 									#如果第二个参数(起始杆)上还有圆盘，则
    		moveDisk(num-1, fromPole, withPole, toPole)	#将起始杆上除了最下面的圆盘全部移到中间杆
    		print("将圆盘从", fromPole, "移到", toPole)	#将原来在最底层的最大圆盘移动到目标杆
    		moveDisk(num-1, withPole, toPole, fromPole)	#再将位于中间杆的圆盘移动到最大圆盘的上面
    
    # 移动次数为2**n-1，n为圆盘个数，此例中为3，则共要移动7次
    moveDisk(3, "A", "B", "C")							#初始有3个从上到下依次变大的圆盘在A杆位置

**结果为：**

将圆盘从 A 移到 B
    将圆盘从 A 移到 C
    将圆盘从 B 移到 C
    将圆盘从 A 移到 B
    将圆盘从 C 移到 A
    将圆盘从 C 移到 B
    将圆盘从 A 移到 B

**示例11：普通递归最少硬币数找零法，需要67716925次递归调用，存在大量重复计算。**

def minimumChangeMethod(change_list, change):
    	if change in change_list:											#若有待找零面值的硬币，则
    		return 1
    	else:											
    		for i in [c for c in change_list if c < change]:				#循环小于要找零面值的硬币
    			minnum = 1 + minimumChangeMethod(change_list, change - i)	#数量加1并递归减去此面值的找零值
    	return minnum
    
    change_list = [1, 5, 10, 25]											#美分面值列表
    print(minimumChangeMethod(change_list, 63))								#找零63美分

**结果为：**

**示例12：查表法递归最少硬币数找零，只需要221次递归函数调用，使用了一种叫做“函数值缓存”，或者一般称为“缓存”的方法改善了程序的性能。也可用其他算法，如动态规划**

def minimumChangeMethod2(change_list, change, knownResults):
    	if change in change_list:								#若有待找零面值的硬币，则
    		knownResults[change] = 1 							#该找零值的最小找零数为1
    		return 1
    	elif knownResults[change] > 0:							#值大于0说明已记录该找零值的最小找零数
    		return knownResults[change]							#返回表中已知找零值的最小找零数
    	else:											
    		for i in [c for c in change_list if c < change]:	#循环小于要找零面值的硬币
    			minnum = 1 + minimumChangeMethod2(change_list, change - i, knownResults)	#数量加1并递归减去此面值的找零值
    			knownResults[change] = minnum 					#将change值的最小找零数存入list中待用
    	return minnum
    
    change_list2 = [1, 5, 10, 25]								#美分面值列表
    knownResults = [0] * 64 									#初始化已知找零表，64是因为最多需要63个1美分加0索引的1个0，共64
    print(minimumChangeMethod2(change_list2, 63, knownResults))	#找零63美分

**结果为：**

[20190412115707918.png_pic_center]: /images/20220220/c5edcad0529547e59455d7b0bb59fbae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4ODgyMzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20220220/7f6de9058311480bbf7f0014edcdb586.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4ODgyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220220/22a4408778474d28834dc8fa4cd30567.png