目录
一、基本介绍
二、递归能解决什么问题？
三、递归案例
1、打印问题
2、阶乘问题
四、递归重要规则
五、课堂练习
1、斐波那契数
2、猴子吃桃问题
3、汉诺塔
一、基本介绍
1、简单地说：递归就是函数自己调用自己，每次调用时传入不同的值
2、递归有助于编程者解决复杂问题，同时可以让代码变得简洁
二、递归能解决什么问题？
1、各种数学问题，如8皇后问题，汉诺塔，阶乘问题，迷宫问题等等
2、各种算法中也会使用到递归，如快排，归并排序，二分查找，分治算法等
3、将用栈解决的问题->递归，代码比较简洁
三、递归案例
1、打印问题
# 打印问题
def test(n):if n>2:test(n-1)print("n =", n)# 调用test(4)
test(4)
2、阶乘问题
# 阶乘问题
def factorial(n):if n==1:return 1else:return factorial(n-1)*n# 打印4的阶乘
print(factorial(4))
四、递归重要规则
1、执行一个函数时，就创建一个新的空间(栈空间)
2、函数的变量是独立的，比如，变量n
3、递归必须向退出递归的条件逼近，否则就是无限递归，就会出现RecursionError: maximum recursion depth exceeded
4、当一个函数执行完毕，或遇到return，就会返回，遵守谁调用，就将结果返回给谁
五、课堂练习
1、斐波那契数
请使用递归的方式求出斐波那契数1,1,2,3,5,8,13...给你一个整数n，求出它的值是多少？
# 斐波那契数
def fbn(n):"""功能：返回n对应的斐波那契数:param n::return: """if n==1 or n==2:return 1# 如果n>2，则对应的斐波那契数为n-1和n-2对应的斐波那契数的和else:return fbn(n-1)+fbn(n-2)# 完成测试
print(fbn(7)) # 132、猴子吃桃问题
猴子吃桃问题：有一堆桃子，猴子第1天吃了其中的一半，并再多吃一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，想再吃时(即还没有吃)，发现只有1个桃子了。问题：最初有多少个桃子？
# 猴子吃桃问题
"""思路分析：1、day==10时，有桃子数 12、day==9时，day9-day9/2-1=day10有桃子数 day9=(day10+1)*23、day==8时，有桃子数 day8=(day9+1)*2
"""# 定义函数，返回对应天数对应的桃子数
def peach(day):if day==10:return 1# 如果是1<=day<10,的范围就是从后一天开始推导else:return (peach(day+1)+1)*2# 完成测试
print("最初的桃子数为：", peach(1)) # 15343、汉诺塔
# 汉诺塔
def hanoi_tower(num, a, b, c):"""输出指定 num个盘子的移动顺序:param num: 指定盘子数:param a: 表示A柱子:param b: 表示B柱子:param c: 表示C柱子:return:"""# 如果只有一个盘子if num == 1:print("第1个盘从:", a, "->", c)else:# 有多个盘，我们认为只有两个，上面所有的盘和最下面的盘# 移动上面所有的盘从A移动到B柱子，这个过程会借助到C柱子hanoi_tower(num - 1, a, c, b)# 移动最下面的盘，从A移动到C柱子print(f"第{num}个盘从: {a} -> {c}")# 把上面所有的盘从B移动到C柱子，这个过程会借助到A柱子hanoi_tower(num - 1, b, a, c)# 完成测试
hanoi_tower(3, "A", "B", "C")
