b站視頻：https://www.bilibili.com/video/BV1iS4y1e7MJ/?spm_id_from=333.999.0.0&vd_source=1717654b9cbbc6a773c2092070686a95

# 遞歸的定義：其實就是自己調用自己，一般用函數的形式來進行
"""
特點：
1、一定要有遞推式（顯示、隱式，也有過程）
2、一定要有遞歸的出口（為了避免一直執行，一定要中止程序）（一般要寫在函數的開頭）
3、一定要定義函數（函數自己調用自己）
4、比較耗內存(斐波那契數列重復計算f(3))
"""
"""
遞歸需要注意的地方：
1、會耗費大量的內存(重復計算)，所以用遞歸一定要謹慎，如果電腦內存不夠大，就不要用遞歸（例如計算斐波那契數列）
"""# 舉例
"""
1、遞推式：
f(1)=1
f(2)=f(1)+1
f(3)=f(2)+1
f(4)=f(3)+1
.
.
.
f(n)=f(n-1)+12、出口
f(1)=1
"""def f(n):# 先寫遞歸的出口if n == 1:return 1else:return f(n-1) + 1a = f(5)
print(a)# 斐波那契數列（會重復計算很多f(2)+f(1)）
def f(n):if n == 1:return 0elif n == 2:return 1else:return f(n - 1) + f(n - 2)print(f(6))# 小明一次最多能上三層樓梯，爬到第n層能有多少種爬法
def f(n):if n == 1:return 1elif n == 2:return 2elif n == 3:return 4else:return f(n - 1) + f(n - 2) + f(n - 3)print(f(5))# 冒泡排序（使用遞歸）
def f(m1, m2):global list1# 遞歸出口if m1 == m2:return# 遞推式，沒有公式，是一個過程for i in range(m1, m2):if list1[i] > list1[i + 1]:list1[i], list1[i + 1] = list1[i + 1], list1[i]# 遞歸f(m1, m2 - 1)list1 = [12, 11, 5, 6, 7, 18]
f(0, len(list1) - 1)
print(list1)# 遞歸：求和，求最大值
def f(n):if n == 1:return 1else:return n + f(n - 1)print(f(10))list1 = [12, 14, 15, 8, 7]def f(n):if n == 1:return list1[0]else:return max(f(n - 1), list1[n - 1])print(f(len(list1)))# 因式分解
num = 1def f(m1, m2):global num# 循環結束就是出口，所以不寫for i in range(m1, m2):if m2 % i == 0 and m2 // i >= i:num += 1f(i, m2 // i)f(2, 36)
print(num)