遞歸函數
在函數內部，可以調用其他函數。如果一個函數在內部調用自身本身，這個函數就是遞歸函數。
遞歸函數特性：
必須有一個明確的結束條件；每次進入更深一層遞歸時，問題規模相比上次遞歸都應有所減少相鄰兩次重複之間有緊密的聯繫，前一次要為後一次做準備（通常前一次的輸出就作為後一次的輸入）。遞歸效率不高，遞歸層次過多會導致棧溢出（在計算機中，函數調用是通過棧（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 <module> 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}可見：
在迭代中，後調用的函數先返回。除了最後一次調用的函數有了正確的返回外，之前的函數都沒有 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)
1t = ex(999)
Traceback (most recent call last):File "E:\Work\Coder\Test\test4.py", line 14, in <module>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。