前段時間，有小夥伴留言，想了解一些有關Python遞歸函數的知識。最近，小編也惡補了一些這方面的內容。說實話，對於遞歸的認識過程，確實能讓我們從中探索出一些很有意思的內容。今天，我們來一探究竟。
01什麼是遞歸？
關於遞歸，網上有一大堆描述資料，很專業，也很詳細。感興趣的小夥伴可以隨手搜一搜。但是，用我們自己聽得懂的話來講，就是「自己調用自己」的方式；那麼，很容易理解，遞歸函數就是在函數實現過程中，直接或間接調用了函數本身的函數。
【舉個例子】我們知道，國外有一個很出名的數學家高斯，在他9歲的時候，用很短的時間計算出了小學老師布置的任務，對自然數從1到100的求和。
他所使用的方法是：對50對構造成和101的數列求和（1＋100，2＋99，3＋98……），同時得到結果：5050。
「數學王子」並非浪得虛名，他9歲時的思維方式確實很獨特。在數學方面，以他名字「高斯」命名的成果達110個，屬數學家中之最。
我們今天不討論這個，回到正題，如何用遞歸的思路解決這個問題呢？作為普通人，我們思考這個問題的方式應該是這樣的：
很簡單，不是嗎？解決遞歸問題就三點：
【首先】確定你要幹啥？就是定義一個函數fn(n)，你要用fn(n)實現哪個功能？
【其次】確定限定範圍！不要被參數n嚇住，它沒那麼可怕，僅僅代表一個數而已。這個限定範圍就是遞歸開始和結束的條件（即上例中的1和100）。
【最後】確定函數等價關係。遞歸的過程實際是不斷縮小參數的過程，這一步的終極目標就是確定參數n和參數n-1之間的關係。
一位從11歲就開始寫程序的「神童」L Peter Deutsch這樣描述遞歸：「Iterative is human, recursive is God.」翻譯過來就是「迭代的是人，遞歸的是神」。這個大牛把遞歸的使用提升到了「神」的高度。
其實也沒這麼誇張，遞歸作為一種奇妙的思維方式，我們總是驚嘆於它描述問題的能力和編寫代碼的簡潔（在實際應用中，它確實能減少很多不必要的代碼，看這個例子的Python實現）。
但在實際應用中，要想真正領悟遞歸的精髓，達到靈活運用的境界，其實並不容易。這其實就是大牛將遞歸提升到「神」的高度的真正原因。
我們先來看下上面例子的Python實現。
02Python解決高斯求和問題！
問題理清楚了，實現起來就簡單多了！我們將求解n以內自然數之和的問題，定義一個函數fn(n)，n是需要求解的最大數（此例中n為100）。那麼，解決該問題有以下2種情況：
當n=1時，fn(1) = 1;當n>1時，fn(n) = fn(n-1) + n程序原始碼如圖所示
沒錯，幾行代碼搞定了，上例的輸出結果就是5050。
03哪些問題可以使用遞歸方法來求解？
理論上來講，類似這樣的問題可以使用遞歸方法來解決：
首先，大問題可以分解為相同方法解決的一系列小問題。而大問題解決需要一系列小問題解決作為前提；
其次，有明確的界定範圍，前提必須是最終的大小問題有解。
很繞口，舉幾個生活方面的例子，如果碰上問題與這個例子相似，那麼，用遞歸方法解決就沒錯。
案例一：剝洋蔥。我想要拿到洋蔥芯，別問我為什麼要拿？現實是我只能從洋蔥的最外層入手，一層一層剝。而剝洋蔥的方法各層都一樣。
案例二：類似俄羅斯套娃的問題。我想拿到最裡面最小的娃娃，得先打開最外層的套娃。而我每次打開套娃使用的方法是一樣的。
案例三：你在一個網紅小吃店門口排隊，很長的隊伍，曲曲折折你數不清前面排了多少人，你前面的人也不知道自己是第幾個，但他也想知道，假定你前面排隊的人都想知道自己是第幾個，則從你開始，一個一個往前問，當問到第一個排隊的時，他從1開始一個個往前反饋，知道反饋到你，這時候你前面的人就都知道自己是第幾個了。
這些問題很通俗易懂，還有哪些經典編程案例呢？作為Python初學者，「樹」的定義、等比等差數列、階乘、Fibonacci數列等等，這些問題，我們同樣是可以通過遞歸方式去解決的。下面，我們舉幾個稍微複雜的例子。
04遞歸方法的經典案例
【案例一】求某數的階乘
def factorial(n):
''' n表示要求的數的階乘 '''
if n==1:
return n
return n * factorial(n-1)
【案例二】斐波那契數列
def fabonacci(n):
''' n為斐波那契數列 '''
if n <= 2:
v = 1
return v
return fabonacci(n-1)+fabonacci(n-2)
【案例三】二分法查找
data = [1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,data,number):
'''min表示有序列表頭部索引
max表示有序列表尾部索引
data表示有序列表
number表示需要尋找的元素
'''
mid = (min + max)// 2
if mid == 0:
return 'None'
elif data[mid] < number:
print('向右側找！')
return dichotomy(mid,max,data,number)
elif data[mid] > number:
print('向左側找！')
return dichotomy(min,mid,data,number)
else:
print('找到了%s'% data[mid])
return
res = dichotomy(0,len(data),data,123)
print(res)
05遞歸函數的局限性
上面講解了遞歸的特點和一些案例，但是遞歸方法並不是每一個適用問題都可以解決的。它也有一些局限性。
在計算機中，函數調用時通過棧(stack)這種數據結構實現的，每當進入一個函數調用，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由於棧的大小不是無限的，所以，遞歸調用的次數過多，就會導致棧溢出。
在進行二分法查找時，如果需要查找的數據不在提供的列表中，當多次查找達到棧的極限時，就會棧溢出，拋出異常。
那麼，如何獲取默認最大遞歸限制呢？
import sys
print(sys.getrecursionlimit())
輸出：3000
其實，還可以設置，但是對於新手來講，這裡就最好不要設置了。使用函數如下：
sys.setrecursionlimit(999999999)
print(sys.getrecursionlimit())
這個設置對於我們問題解決是起不到任何作用滴！自己分析……
好了，今天的內容就到這裡了，喜歡Python編程的小夥伴關注我，後續會推出更加精彩的內容。還有哪些有意思的遞歸用法呢？歡迎大家下方留言！
轉載請註明出處，百家號：Python高手養成