递归函数
2024年7月5日大约 3 分钟
函数调用函数自身，这种方式称为递归，这种函数称为递归函数
递归函数使用过程中，需要找到不变的规律和停止递归的边界条件，因为函数自身调用自身，函数本身的结构不变，只是每次传的参数改变啦
递归实现过程(扩展)：利用栈的思想，先找边界条件，同时将后面的任务存起来，一直到最前面的边界条件，然后回去，每次从栈中取任务，进行计算，一直到最后一个任务取完，结果也计算完毕
递归过程:
- 递归前进段
- 递归边界条件
- 递归返回段
案例讲解
整数转换为字符串
将一个整数转换为字符串，如 345转换为"345"
def trans(num):
if num // 10 == 0:
return '%s'%num
else:
return trans(num//10)+'%s'%(num%10)树的高度
递归求二叉树深度
def getHeight(self,root):
if root is None:
return 0
else:
return max(self.getHeight(root.left), self.getHeight(root.right)) + 1递归实现吸烟问题
吸烟有危害，不仅仅危害人体健康，还会对社会产生不良的影响。吸烟还很容易引起喉头炎、气管炎，肺气肿等问题； 那么现在假设人一生抽烟10000根达到极限峰值，再抽一根烟就像压倒骆驼的最后一根稻草，会使人体爆发疾病问题； 每天一个人抽烟的个数都比前天多一根（第一天抽一根），且一周只有工作日（周一~周五）会吸烟； 请使用递归的方式求出一个人按照以上方式抽烟达到10000根，爆发疾病需要历经多少天
def smoker(day, count, amount):
"""
递归解决吸烟问题
:param day: 当前的天数
:param count: 当天的吸烟数量
:param amount: 总计的吸烟数量
:return: 吸到10000根烟的天数
"""
if amount >= 10000:
# 如果吸烟总数大于10000， 返回天数
return day
else:
day += 1 # 每吸一次烟，天数加1
if day % 7 != 6 and day % 7 != 0:
# 只有周六，周日不吸烟，判断不是周六，也不是周日
count += 1 # 当天吸烟的数量
amount += count # 目前为止，吸烟的总数量
return smoker(day, count, amount)
print(smoker(1, 1, 1)) # 第1天，吸了1根烟，总共吸了1根烟青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
# 这个问题，本质是一个斐波那契数列数列求第n项值的问题，如果用递归求，将会超出时间限制
# 因此，直接用循环求即可
class Solution:
def numWays(self, n: int) -> int:
a = 1
b = 1
for i in range(n):
a, b = b, a+b
return a % 1000000007汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
class Solution:
def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
n = len(A)
self.move(n, A, B, C)
# 定义move 函数移动汉诺塔
def move(self,n, A, B, C):
if n == 1:
C.append(A[-1])
A.pop()
return
else:
self.move(n-1, A, C, B) # 将A上面n-1个通过C移到B
C.append(A[-1]) # 将A最后一个移到C
A.pop() # 这时，A空了
self.move(n-1,B, A, C) # 将B上面n-1个通过空的A移到C