什么是遞歸？
遞歸（英語：Recursion）姚淆，又譯為遞回屡律，在數(shù)學(xué)與計算機科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法搏讶。遞歸一詞還較常用于描述以自相似方法重復(fù)事物的過程霍殴。
在用代碼實現(xiàn)時来庭，遞歸一般是直接或者間接調(diào)用函數(shù)自身。遞歸的應(yīng)用也很廣泛面睛，比如在 DFS 深度優(yōu)先搜索尊搬、前中后序二叉樹遍歷等。
相關(guān)實例
電影院找座位排號問題
當(dāng)你自己去電影院看電影時(不知道為啥是自己去看電影)幌墓，影廳一般很黑，自己按照電影票上的座位號坐下了蜡饵，健忘的你又把排號忘了胳施，而你又有點強迫癥，就想知道自己坐在哪一排焦辅，怎么辦？看電影票筷登，太黑看不見哩盲，看手機購買訂單，恰巧是線下買的惠险。最簡單的辦法就是問你前面那個人是多少排娱两，如果他也不知道金吗，就再問前前一排摇庙，一直問到第一排的觀眾，每一排的觀眾再把自己所在的排號返回來卫袒，這樣，你就知道自己是第幾排了宝穗，這就是遞歸的思想逮矛。（說得有點啰嗦了）
遞歸的思想就是转砖，把一個問題分解成一個個的子問題和子子問題，然后這些子問題逐級返回，得到最終結(jié)果汞窗。遞歸問題還需要一個終止條件仲吏，比如在電影院這個問題中蝌焚，終止條件就是問到第一排的觀眾。除此之外品腹，每個子問題的求解思路都必須完全一樣红碑。下面總結(jié)一下遞歸需要滿足的幾個條件：
- 一個問題的解可以分解為幾個子問題的解析珊。
- 這個問題與分解后的子問題，除了數(shù)據(jù)規(guī)模不同外惧浴，求解思路完全一樣奕剃。
- 存在遞歸終止條件。
遞歸算法的核心就是根據(jù)一個問題歸納出該問題求解的遞推公式柿顶，對于這個問題嘁锯，假如你在第 f(n) 排，那么 f(n) = f(n-1)+1家乘，這就是遞推公式仁锯，另外終止條件是 n==1笆载，現(xiàn)在用代碼實現(xiàn)一下涯呻。
def cinema(n):
if n == 1:
return 1
return cinema(n-1) +1
result = cinema(14)
print (result)
上臺階問題
上臺階問題也相當(dāng)于斐波那契問題复罐，具體描述是這樣的：有一個 n 級臺階雄家，一個人從第一級往上走趟济，每次只能走 1 級或者 2 級，問有多少種走法顷编。
下面用逆向思維來考慮這個問題媳纬，先看最上面那個臺階 f(n) ，上這級臺階有兩種方法<1>茅糜，一是邁 1 級上去 f(n-1)素挽，二是邁 2 級上去 f(n-2)，這兩種方法又分別有兩種相同的子方法<2>缩赛，一次分析下去贮庞，一直到第 1 級臺階和第 2 級臺階結(jié)束。<3>
我標(biāo)出的 <1>、<2>卤材、<3> 恰好符合遞歸的條件,遞推公式為 f(n) = f(n-1)+f(n-2)扇丛，下面用代碼實現(xiàn)一下。
def Fbsq(n):
if (n < 0):
return -1
elif (n == 1):
return 1
elif (n == 2):
return 2
else:
return Fbsq(n-1) + Fbsq(n-2)
result = Fbsq(10)
print (result)
警惕堆棧溢出
在棧那節(jié)這種說過较屿，函數(shù)調(diào)用是通過棧來實現(xiàn)的，遞歸需要不斷地進行函數(shù)調(diào)用购啄，相當(dāng)于不斷地壓棧狮含，很容易造成堆棧溢出，會造成系統(tǒng)性的崩潰几迄，所以遞歸求解不適合用在數(shù)據(jù)規(guī)模大的地方映胁。
為了防止堆棧溢出的出現(xiàn)屿愚，可以限制遞歸的深度务荆，但治標(biāo)不治本，數(shù)據(jù)規(guī)模大的話娱据，還是不用遞歸為好中剩。
警惕重復(fù)計算
看一個這個例子：
里面 f(3) 被多次計算结啼，會無故消耗代碼運行時間郊愧，為了避免這種重復(fù)計算的情況出現(xiàn)井佑，可以將已經(jīng)計算的 f(n) 保存在一個散列表中，當(dāng)調(diào)用 f(n) 時焦蘑，可以先看看散列表中有沒有例嘱，沒有的話再計算狡逢。
遞歸代碼寫成非遞歸的形式
遞歸代碼都能寫成非遞歸的形式拼卵，例如電影院問題间学，寫成非遞歸的形式為：
def Ncinema(n,result):
for i in range(n):
result += 1
return result
number = Ncinema(14,0)
print (number)
小結(jié)
遞歸需要滿足三個條件殷费，遞歸用在數(shù)據(jù)規(guī)模較小的情況下详羡，要注意堆棧溢出和重復(fù)計算，每個遞歸都能寫成非遞歸的形式嘿悬。
