遞歸函數 什麼是遞歸 瞭解什麼是遞歸 ： 在函數中調用自身函數 最大遞歸深度預設是 997/998 —— 是 python 從記憶體角度出發做得限制 能看懂遞歸 能知道遞歸的應用場景 初識遞歸 —— 二分法的例子 演算法 —— 二分查找演算法 三級菜單 —— 遞歸實現 我們先來看一個簡單的遞歸函數 測試遞 ...
遞歸函數
什麼是遞歸
瞭解什麼是遞歸 ： 在函數中調用自身函數
最大遞歸深度預設是 997/998 —— 是 python 從記憶體角度出發做得限制
能看懂遞歸
能知道遞歸的應用場景
初識遞歸 —— 二分法的例子
演算法 —— 二分查找演算法
三級菜單 —— 遞歸實現
我們先來看一個簡單的遞歸函數
#可以執行下，看下與遞歸函數執行的結果有什麼不同 while True: print('從前有座山') #一個簡單的遞歸函數 def story(): print('從前有座山') story() print(111) #執行不到這句話 story() #RecursionError: maximum recursion depth exceeded while calling a Python object # 遞歸的錯誤，超過了遞歸的最大深度
測試遞歸函數的深度
#測試以下 python 中的遞歸深度 預設 997 #修改遞歸限制 import sys sys.setrecursionlimit(100000) #不要改 n=0 def rec(): global n print('從前有座山') n +=1 print(n) rec() rec() # 如果遞歸次數太多，那麼就不適合使用遞歸來解決問題 # 遞歸的缺點 ： 占記憶體 # 遞歸的優點： 會讓代碼變簡單
遞歸的邏輯
當你想解決一個問題時，需要知道另一個問題的答案
且下一個問題和前面的問題處理方法一致
遞歸是自上往下解決問題的
好比這樣的問題
張三 多大 n = 1 age(1) = age(2)+2 = age(n+1) + 2 張三 比 李四 大兩歲 李四 多大？ n = 2 age(2) = age(3) + 2 = age(n+1) +2 李四 比 王五 大兩歲 王五 多大 n = 3 age(3) = age(4) + 2 = age(n+1) +2 王五 比 趙六 大兩歲 趙六 多大？ 趙六 40 了 n = 4 age(4) = 40
我們把上面的邏輯寫一個遞歸函數
def age(n): if n == 4: return 40 elif n >0 and n < 4: return age(n+1) + 2 print(age(1)) #輸出結果 46
這個 46 是怎麼產生的呢？我們下麵來看
def age(1): if 1 == 4: return 40 elif 1 > 0 and 1 < 4: return 46 #於是最終得到 46 的結果 def age(2): if 2 == 4: return 40 elif 2 >0 and 2 < 4: return age(3) + 2 # age(3) 的返回結果加 2 得到 44，返回給 age(1) def age(3): if 3 == 4: return 40 elif 3 >0 and 3 < 4: return age(n+1) + 2 #4、age(4) + 2 得到 42 返回給age(2) def age(4): if 4 == 4: #2、發現下麵判斷不在滿足條件 return 40 #3、於是返回 return 40，註意：這裡返回給了調用著 age(3) elif n >0 and n < 4: return age(n+1) + 2 #1、這裡 age(3+1) 得到 age(4) ，再次調用
小結：
超過最大遞歸限制的報錯
只要寫遞歸函數，必須要有結束條件。
返回值
1、不要只看到return就認為已經返回了。要看返回操作是在遞歸到第幾層的時候發生的，然後返回給了誰。
2、如果不是返回給最外層函數，調用者就接收不到。
3、需要再分析，看如何把結果返回回來。
二分查找演算法
什麼叫演算法
計算的方法 ： 人腦複雜 電腦簡單
我們現在學習的演算法 都是過去時
瞭解基礎的演算法 才能創造出更好的演算法
不是所有的事情都能套用現成的方法解決的
有些時候會用到學過的演算法知識來解決新的問題
二分查找演算法 必須處理有序的列表
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
基礎版，列表的 k 的下標亂了
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88] def find(lis,aim): #獲取中間值 mid = len(lis)//2 #如果中間值大於 aim if lis[mid] > aim: new_lis = lis[:mid] find(new_lis,aim) elif lis[mid] < aim: new_lis = lis[mid + 1:] find(new_lis,aim) else: print('找到了：'+ str(aim) + ' 所在位置為：'+ str(mid)) find(k,66)
升級版，解決了下標問題
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88] def find(lis,aim,start = 0,end = len(k)): #獲取中間值 mid = (end - start)//2 + start #如果中間值大於 aim if lis[mid] > aim: find(lis,aim,start = start,end = mid-1) elif lis[mid] < aim: find(lis,aim,start = mid + 1,end = end) else: print('找到了：'+ str(aim) + ' 所在位置為：',mid) find(k,18) find(k,43)
繼續升級
end 的問題
我們不希望每次找一個列表的都要修改函數中額 len(k) 這樣函數就沒有了可用性
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88] def find(lis,aim,start = 0,end = None): end = len(lis) if end is None else end #獲取中間值 mid = (end - start) // 2 + start #中間值大於 aim if lis[mid] > aim: find(lis,aim,start = 0,end = mid - 1) elif lis[mid]< aim: find(lis,aim,start= mid + 1,end = end) else: print('找到了：'+str(aim)+"位於"+str(mid)) find(k,69)
接著升級
找不到所要查找的值怎麼處理
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88] def find(lis,aim,start = 0,end = None): end = len(lis) if end is None else end #獲取中間值 mid = (end - start) // 2 + start if start <= end: #中間值大於 aim if lis[mid] > aim: find(lis,aim,start = 0,end = mid - 1) elif lis[mid]< aim: find(lis,aim,start= mid+1,end = end) else: print('找到了：'+str(aim)+"位於"+str(mid)) else: print('找不到這個值') find(k,68)
最後返回值的問題，因為我們希望最後的結果只是一個我們想要的值
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88] def find(lis,aim,start = 0,end = None): end = len(lis) if end is None else end #獲取中間值 mid = (end - start) // 2 + start if start <= end: #中間值大於 aim if lis[mid] > aim: return find(lis,aim,start = 0,end = mid - 1) elif lis[mid]< aim: return find(lis,aim,start= mid+1,end = end) else: # print('找到了：'+str(aim)+"位於"+str(mid)) return mid else: return'找不到這個值' print(find(k,5))
為了更加瞭解遞歸函數和上面的二分查找法可以拆開上面的函數分析下麵的三種方法
# 67 發生兩次調用 # 66 發生好幾次 # 44 找不到
