當我們碰到諸如需要求階乘或斐波那契數列的問題時，使用普通的回圈往往比較麻煩，但如果我們使用遞回時，會簡單許多，起到事半功倍的效果，這篇文章主要和大家分享一些和遞回有關的經典案例，結合一些資料談一下個人的理解，也借此加深自己對遞回的理解和掌握一些遞回基礎的用法，
一、遞回的簡介
1、遞回的百度百科定義
程式呼叫自身的編程技巧稱為遞回（ recursion），
遞回做為一種演算法在程式設計語言中廣泛應用， 一個程序或函式在其定義或說明中有直接或
間接呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量，
遞回的能力在于用有限的陳述句來定義物件的無限集合，一般來說，遞回需要有邊界條件、遞回前進
段和遞回回傳段，當邊界條件不滿足時，遞回前進；當邊界條件滿足時，遞回回傳，
2、遞回的通俗理解
遞回就是在函式內部呼叫自己的函式被稱之為遞回，
3、幾個關于遞回通俗的比喻
1.我們使用的詞典，本身就是遞回，為了解釋一個詞，需要使用更多的詞，當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，于是你開始查這第二個詞，可惜，第二個詞里仍然有不懂的詞，于是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那么遞回走到了盡頭，然后你開始后退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思，
2.一個小朋友坐在第10排，他的作業本被小組長扔到了第1排，小朋友要拿回他的作業本，可以怎么辦？他可以拍拍第9排小朋友，說：“幫我拿第1排的本子”，而第9排的小朋友可以拍拍第8排小朋友，說：“幫我拿第1排的本子”...如此下去，訊息終于傳到了第1排小朋友那里，于是他把本子遞給第2排，第2排又遞給第3排...終于，本子到手啦！這就是遞回，拍拍小朋友的背可以類比函式呼叫，而小朋友們都記得要傳訊息、送本子，是因為他們有記憶力，這可以類比堆疊，
3.一個洋蔥是一個帶著一層洋蔥皮的洋蔥，
4、最簡單的遞回的實體
# 將 10不斷除以2，直至商為0，輸出這個程序中每次得到的商的值，
def recursion(n):
v = n//2 # 地板除，保留整數
print(v) # 每次求商，輸出商的值
if v==0:
''' 當商為0時，停止，回傳Done'''
return 'Done'
v = recursion(v) # 遞回呼叫，函式內自己呼叫自己
recursion(10) # 函式呼叫
輸出結果：
5
2
1
0
5、遞回的特點
通過以上的介紹，我們大致可以總結出遞回的以下幾個特點：
1、必須有一個明確的結束條件
2、每次進入更深一層遞回時，問題規模(計算量)相比上次遞回都應有所減少
3、遞回效率不高，遞回層次過多會導致堆疊溢位（在計算機中，函式呼叫是通過堆疊（stack）這種資料結構實作的，每當進入一個函式呼叫，堆疊就會加一層堆疊幀，每當函式回傳，堆疊就會減一層堆疊幀，由于堆疊的大小不是無限的，所以，遞回呼叫的次數過多，會導致堆疊溢位）
關于遞回還有兩個名詞，可以概括遞回實作的程序
遞推：像上邊遞回實作所拆解，遞回每一次都是基于上一次進行下一次的執行，這叫遞推
回溯：則是在遇到終止條件，則從最后往回返一級一級的把值回傳來，這叫回溯
二、遞回經典案例
1、遞回求階乘
實體如下：
'''
學習中遇到問題沒人解答？小編創建了一個Python學習交流群：711312441
尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學習教程和PDF電子書！
'''
# 1！+2！+3！+4！+5！+...+n!
def factorial(n):
''' n表示要求的數的階乘 '''
if n==1:
return n # 階乘為1的時候，結果為1,回傳結果并退出
n = n*factorial(n-1) # n! = n*(n-1)!
return n # 回傳結果并退出
res = factorial(5) #呼叫函式，并將回傳的結果賦給res
print(res) # 列印結果
2、遞回推斐波那契數列
實體如下：
# 1，1，2，3，5，8，13，21，34，55，試判斷數列第十五個數是哪個？
def fabonacci(n):
''' n為斐波那契數列 '''
if n <= 2:
''' 數列前兩個數都是1 '''
v = 1
return v # 回傳結果，并結束函式
v = fabonacci(n-1)+fabonacci(n-2) # 由資料的規律可知，第三個數的結果都是前兩個數之和，所以進行遞回疊加
return v # 回傳結果，并結束函式
print(fabonacci(15)) # 610 呼叫函式并列印結果
3、二分法找有序串列指定值
實體如下：
data = https://www.cnblogs.com/python1111/p/[1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,d,n):'''
min表示有序串列頭部索引
max表示有序串列尾部索引
d表示有序串列
n表示需要尋找的元素
'''
mid = (min+max)//2
if mid==0:
return 'None'
elif d[mid]<n:
print('向右側找！')
return dichotomy(mid,max,d,n)
elif d[mid]>n:
print('向左側找！')
return dichotomy(min,mid,d,n)
else:
print('找到了%s'%d[mid])
return
res = dichotomy(0,len(data),data,222)
print(res)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505941.html
標籤：Python
上一篇：【Python實戰】全球疫情資料采集, 并做可視化展示
下一篇：Python自學筆記（蟒蛇書）