詳細解讀Python 遞歸函數！

遞歸函數

在函數內部，可以調用其他函數。如果一個函數在內部調用自身本身，這個函數就是遞歸函數。

遞歸函數特性：

1. 必須有一個明確的結束條件；
2. 每次進入更深一層遞歸時，問題規模相比上次遞歸都應有所減少
3. 相鄰兩次重複之間有緊密的聯繫，前一次要為後一次做準備（通常前一次的輸出就作為後一次的輸入）。
4. 遞歸效率不高，遞歸層次過多會導致棧溢出（在計算機中，函數調用是通過棧（stack）這種數據結構實現的，每當進入一個函數調用，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由於棧的大小不是無限的，所以，遞歸調用的次數過多，會導致棧溢出）

先舉個簡單的例子：計算1到100之間相加之和；通過循環和遞歸兩種方式實現

#!/usr/bin/env python3# 1-100 sumimport sysdef sum_cycle(n): ''' 1 to n,The sum function ''' sum = 0 for i in range(1,n + 1): sum += i return sumdef sum_recu(n): ''' 1 to n,The sum function ''' if n > 0: return n + sum_recu(n - 1)　　　　#調用函數自身 else: return 0print("循環求和：",sum_cycle(100))print("遞歸求和：",sum_recu(100))執行結果：[root@localhost tmp]# ./sum.py循環求和： 5050遞歸求和： 5050

遞歸函數的優點是定義簡單，邏輯清晰。理論上，所有的遞歸函數都可以寫成循環的方式，但循環的邏輯不如遞歸清晰。

***使用遞歸函數需要注意防止棧溢出。在計算機中，函數調用是通過棧（stack）這種數據結構實現的，每當進入一個函數調用，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由於棧的大小不是無限的，所以，遞歸調用的次數過多，會導致棧溢出。

把上面的遞歸求和函數的參數改成10000就導致棧溢出！

[root@localhost tmp]# ./sum.py循環求和： 5050Traceback (most recent call last): File "./sum.py", line 23, in  print("遞歸求和：",sum_recu(1000)) File "./sum.py", line 19, in sum_recu return n + sum_recu(n - 1) File "./sum.py", line 19, in sum_recu return n + sum_recu(n - 1) File "./sum.py", line 19, in sum_recu return n + sum_recu(n - 1) [Previous line repeated 994 more times] File "./sum.py", line 18, in sum_recu if n > 0:RecursionError: maximum recursion depth exceeded in comparison

***解決遞歸調用棧溢出的方法是通過尾遞歸優化，事實上尾遞歸和循環的效果是一樣的，所以，把循環看成是一種特殊的尾遞歸函數也是可以的。

尾遞歸優化：http://www.open-open.com/lib/view/open1480494663229.html

二分法查找大家應該聽說過；就是一種快速查找的方法，時間複雜度低，邏輯簡單易懂，總的來說就是不斷的找出中間值，用中間值對比你需要找的實際值；若中間值大，則繼續找左邊；若中間值小，則繼續找右邊；可以看出二分法就是不斷重複此上過程，所以就可以通過遞歸方式來實現二分法查找了！

今天在 codewar 做題目玩，做到一題時，想試試用遞歸寫，卻發現在函數體內一切正常，可是打印返回值時，打印出來的結果卻是 None 。不明白是在哪裡除了問題了，於是在網上翻了一圈，自己又仔細思考了下整個邏輯。似乎弄清楚了。這裡我來解釋下我的理解。

首先，我來寫一個簡化的遞歸函數，來做用於解釋的案例。

def ex(x): if x > 1: x -= 1 ex(x) else: return xt = ex(5)print(t)

上面的程序邏輯超簡單：判斷輸入的書是否大於 1 ，如果大於 1 則把它減 1 ，然後再判斷。如此不斷遞歸下去。當 x 不大於 1 的時候，返回 x 的大小。

很容易認為返回的 x 打印出來的結果是 1 是不？但是不是的。你可以把上面的代碼運行下，打印出來的結果是：

None

為什麼是這樣的呢？我的理解是：

當我們在 t = ex(5) 的時候，調用了一次函數。如果函數直接返回 t = 1，那是木有問題的。問題是，程序在這裡返回數據。反而又去調用了一次函數本身。這次調用的的是 ex(4) 然後一直調用的 ex(1) 這時候程序終於運行到了 return 這裡。那這次 return 給了誰呢？答案是誰都沒有給。因為我們沒有設置 t = ex(1)， 所以函數的 return 回的數據就這麼丟失了。

而我們調用的 t = ex(5) 呢，因為它的 if > 1 是成立的，所以直接跳過了了 else: return x ，等於這一次調用，是沒有用到 return 的。而在 Python 中規定，如果一個函數體沒有 return 的時候，那它的 return 就是 None 。這也就是為什麼，我們運行上面的程序的時候，得到的結果是 None 。

為了證明這點，我們可以去寫一個程序，去嘗試獲得迭代到 ex(1) 這次調用時 ex(1) 所返回的值。程序如下：

t = {}def ex(x): global t if x > 1: x -= 1 t[x] = ex(x) else: return xex(10)print(t)

在程序中，我們用字典，把 ex(x) 每次調用所返回的數據記錄了下來。結果如下：

{1: 1, 2: None, 3: None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None}

可見：

1. 在迭代中，後調用的函數先返回。
2. 除了最後一次調用的函數有了正確的返回外，之前的函數都沒有 return ，所以返回的都是 None。

那如何正確地返回迭代出來的數據呢？答案是：一層一層第把最後一次調用返回出來。代碼如下：

def ex(x): if x > 1: x -= 1 return ex(x) else: return xt = ex(5)print(t)

結果為：

1

為什麼這次能正確呢？因為第一次調用 ex(x) 的時候，它返回的是ex(x-1)，下一次調用返回了 ex(x-2) 一路攜手交傳，最終把 ex(1) return 給了 t ，這個時候就等於 t = ex(1) 了，自然就得到了正確的結果了。

嗯，本文就到這裡要結束了。最後說一下， Python 的確不喜歡迭代。所以它嚴格限制了迭代的次數。我電腦上，只要迭代的次數超過 999 ，就會報錯，如下：

t = ex(998)

1

t = ex(999)

Traceback (most recent call last):File "E:\Work\Coder\Test\test4.py", line 14, in t = ex(999)RecursionError: maximum recursion depth exceeded in comparison

***解決遞歸調用棧溢出的方法是通過尾遞歸優化，事實上尾遞歸和循環的效果是一樣的，所以，把循環看成是一種特殊的尾遞歸函數也是可以的。

尾遞歸優化：http://www.open-open.com/lib/view/open1480494663229.html

二分法查找大家應該聽說過；就是一種快速查找的方法，時間複雜度低，邏輯簡單易懂，總的來說就是不斷的找出中間值，用中間值對比你需要找的實際值；若中間值大，則繼續找左邊；若中間值小，則繼續找右邊；可以看出二分法就是不斷重複此上過程，所以就可以通過遞歸方式來實現二分法查找了！

#!/usr/bin/env python3#The binary search functiondef Binary_Search(data_source,find_n): if len(data_source) >= 1: #判斷列表長度是否大於1，小於1就是一個值 mid = int(len(data_source)/2) #獲取列表中間索引；奇數長度列表長度除以2會得到小數，通過int將轉換整型 if find_n > data_source[-1]: #判斷查找值是否超出最大值 print('{}查找值不存在！'.format(find_n)) exit() elif find_n < data_source[0]: #判斷查找值是否超出最小值 print('{}查找值不存在！'.format(find_n)) exit() if data_source[mid] > find_n: #判斷列表中間值是否大於查找值 #print('查找值在 {} 左邊'.format(data_source[mid])) Binary_Search(data_source[:mid],find_n) #調用自己，並將中間值左邊所有元素做參數 elif data_source[mid] < find_n: #判斷列表中間值是否小於查找值 #print('查找值在 {} 右邊'.format(data_source[mid])) #調用自己，並將中間值右邊所有元素做參數 Binary_Search(data_source[mid:],find_n) else: print('找到查找值',data_source[mid]) #找到查找值 else: print('{}查找值不存在！'.format(find_n)) #特殊情況，返回查找不到Data = [22,12,41,99,101,323,1009,232,887,97]Data.sort() #列表從小到大排序Binary_Search(Data,323) #查找323執行結果：[root@localhost tmp]# ./binary_search.py 找到查找值 323

好了，今天的知識就分享到這裡，歡迎關注愛編程的南風，私信關鍵詞：學習資料，獲取更多學習資源，如果文章對你有有幫助，請收藏關注，在今後與你分享更多學習python的文章。同時歡迎在下面評論區留言如何學習python。

閱讀更多 愛編程的南風 的文章

關鍵字: 數據結構 Python Line