小時候，你一定聽說過這樣一個故事：“從前有座山，山上有座廟，廟里有個老和尚，正在給小和尚講故事呢，講的什么故事呢：‘從前有座山，山上有座廟...’”
或許，你一定有過這樣的經(jīng)歷，每逢節(jié)假日回家，坐公交的時候，人都特別多。記得那一次，你著急回家，不得不從后面的門上了車。上車之后，你得刷卡呀，人太多過不去咋辦，你只能把卡傳給你前面的人讓他幫你刷，你前面的人也夠不著咋辦，只能再繼續(xù)往前傳，就這樣，終于傳到最后一個人手里，刷了卡，并且卡還得原路返回，還到你手上。
想想這兩個故事，再想想編程的時候，在函數(shù)中調(diào)用函數(shù)本身，是不是有點似曾相識了！這就是遞歸。
遞歸有三個要素。
以最常見的斐波那契數(shù)列，來通俗的解釋一下這三個要素。
斐波那契數(shù)列：
1,1,2,3,5,8,13,21...
第一，要知道你寫的函數(shù)是干什么的。
f(1)=1??
f(2)=1?
f(3)=2?
f(4)=3?
f(5)=5
那么，f(n)=?
顯然，我們的函數(shù)就是要求得f(n)的值。
第二，遞歸表達(dá)式
f(1)=1??
f(2)=1
f(3)=f(1)+f(2)=2?
f(4)=f(2)+f(3)=3?
f(5)=f(3)+f(4)=5
...
f(n)=f(n-2)+f(n-1)
這就是遞歸表達(dá)式了！是不是感覺也不是很難呀！
第三，遞歸的出口
要知道f(n)，就得知道f(n-1)和f(n-2)，以此類推，最后會到f(1)和f(2)停止。所以f(1)=f(2)=1就是遞歸的出口了。
對照源碼看一下：
現(xiàn)在，你知道了斐波那契數(shù)列。
那么，試著想一下這個題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
分析一波：
青蛙每次跳的時候都有兩種選擇。
第一種選擇：第一次跳一個臺階，剩下的n-1個臺階的跳法有f(n-1)種。
第二種選擇：第一次跳兩個臺階，剩下的n-2個臺階的跳法有f(n-2)種。
所以，青蛙的跳法就是這兩種跳法之和，即 f(n) = f(n-1) + f(n-2)。
臥槽，是不是又似曾相識了哇！褪下那一層神秘的面紗，又回到了斐波那契數(shù)列。接下來，就是和上面一樣的步驟了。
說了這么多，再來看一個例子（階乘的計算）鞏固一下。
第一個要素：函數(shù)的作用：計算階乘
第二個要素：遞歸表達(dá)式：f(n)=f(n-1)*n
第三個要素：遞歸出口：f(1)=1
對照源碼：
總結(jié)一下：
編寫遞歸代碼的關(guān)鍵就是不要把自己繞進(jìn)去，正確姿勢是寫出遞推公式，找出終止條件，然后再翻譯成遞歸代碼。
1、遞歸的三要素
2、斐波那契數(shù)列、青蛙跳臺階、計算階乘
要想理解遞歸，請先理解遞歸。
你看懂了嗎？
想要了解更多通俗易懂的編程知識，請關(guān)注公眾號【GitPython】
