遞迴

遞迴不是一種演算法，而是一種程式設計方法。在很多演算法中，都會使用遞迴來完成，這裡我們會從如何掌握遞迴開始來說說掌握要領，但更多的是需要透過手敲程式碼來練習。

另外，遞迴能做到的用普通迴圈的方式同樣可以做到，遞迴只是讓程式碼或者解決方案看起來更清晰，在效能上並沒有什麼優勢。而且在某種情況下，用迴圈可能效能會更好。Leigh Caldwell說過一句話：“如果使用迴圈，程式的效能可能更高；如果使用遞迴，程式可能更容易理。如何選擇要看什麼對你來說更重要。”（https://stackoverflow.com/questions/72209/recursion-or-iteration/72694#72694）

1 兩個條件

什麼情況使用遞迴，如何使用遞迴，是很多新手面對的問題。對於能使用迴圈解決的問題，我們更容易使用迴圈，因為容易想出來，雖然遞迴也可以做到，但因為不常寫，思考模式沒有建立起來，就不會想到，或者想用遞迴但卻無從下手。下面我們來說說使用遞迴的兩個基本條件。

遞迴說白了就是自己呼叫自己，所以這樣的函式在寫的時候很容易出現無限呼叫即無限迴圈的錯誤，報出OOM。

比如我們給了一個數後要遞減打印出來，直到1為止，程式碼如下：

def printNum(i)： print i printNum(i-1)

上面程式碼可以在給定一個數 i 後逐次遞減列印，我們看到除第一次列印使用函式的print外，後續的列印都呼叫了函式本身 printNum，這個就是遞迴條件。但問題是這樣執行起來就沒完沒了了，會在負數的路上一去不回頭。所以，在使用遞迴前，第一件事是要考慮這個遞迴函式的基線條件，也就是終止條件。

在上面例子中，列印到1就是終止條件，那麼程式碼中要加上一個當 i 為1時退出的條件，即基線條件。在不滿足退出的情況下，再使用遞迴條件呼叫自身函式，形成遞迴。完整程式碼如下：

def printNum(i): print i if i <= 0: //基線條件 return else: printNum(i-1) //遞迴條件

上面程式碼可以在達到退出條件就終止，所以在使用遞迴前第一件事要考慮什麼時候退出函式，儘快的做到避免無限迴圈的錯誤。

基線條件即終止條件，或者更好的理解成遞迴條件要去靠近的條件，遞迴中的計算是在遞迴條件中完成的，而計算的目的是不斷的靠近基線條件。

2 棧

為什麼要說棧呢，因為我們要了解遞迴是怎麼呼叫的，所以在遞迴呼叫中，我們要知道什麼是呼叫棧。

棧是一種資料結構，特點是先進後出。新內容從上向下加入，後來的會壓在之前的內容上，取或者呼叫的時候要先將最上面的開始取，取完了要彈出，這樣才能使用下面的內容。上面只是最簡單的介紹，下面舉例詳細說。

比如我們今天有很多事情要做，透過寫便籤的方式記錄下來，然後按照便籤去完成。每個便籤寫完都插在一個朝上的釘子上來固定，這個釘子我們可以理解成棧，每個便籤就是放入的內容，先放在釘子上的會被後面放的蓋住，所以取的時候也是後面的會先被拿出來才能拿後面的，即先進後出（因要原路返回，入口和出口是同一個）。

第一件事是洗漱，我們寫個便籤洗漱放在釘子上，注意，在程式碼方法的呼叫中，不是一下子把所有東西都放到棧中，而是用的時候放入，然後使用，其中又使用到別的方法再放入，然後再使用。例如第一件事我們雖然放入了但不做，想做個早飯先，所以寫了第二個便籤做早飯。接下來就真的開始做早飯了，但做早飯又需要其它的東西，雞蛋和麵包，於是又寫了便籤取雞蛋和麵包放在釘子上，注意這個便籤會壓在之前的做早飯上面，然後又開始呼叫取雞蛋和麵包，按照這個便籤做完後會將取雞蛋和麵包的便籤彈出。然後下一步是煎雞蛋，於是又有個煎雞蛋的便籤插在釘子上，這個便籤會壓在做早飯上面。然後呼叫煎雞蛋便籤，做完後這個便籤會彈出。現在最上面是做早飯便籤，而我們早飯也做完了，所以做早飯便籤也會被彈出。然後就露出洗漱便籤，我們會按照便籤去洗漱，洗完了會彈出這個便籤。以上就是棧的呼叫過程，便籤就是我們呼叫的方法。

如上圖，從左到右就是我們給棧中不斷呼叫方法的過程，方法依次壓入棧，然後依次再從上往下彈出，最後洗漱完就結束了。

3 遞迴呼叫棧

遞迴函式中就使用呼叫棧來呼叫自身函式。比如我們寫一個階乘的函式，忘了階乘的補習下：5的階乘就是從5開始減一相乘，直到1為止，即5x4x3x2x1，3的階乘就是3x2x1，表示上用數字加歎號，如5！、3！。

下面我們就用遞迴來寫一個求階乘的方法：寫之前我們要確定兩件事，一是基線條件，二是遞迴條件。基線條件就是終止遞迴的條件，上面條件已經給出了，就是在乘到1的時候就停止，所以當值為1時就停止即返回。遞迴條件就是逐級減一相乘，引數乘以引數減一即遞迴條件。程式碼如下：

def funDiGui(x): if x == 1: //基線條件 return 1 else: return x * funDiGui(x-1) //遞迴條件

下面我們傳入引數3，來看看funDiGui(3)在呼叫其呼叫棧是如何變化的。

下圖是對函式第一次呼叫：

下圖是對函式第二次呼叫：

程式碼進行到上圖我們發現會遇到基線條件x==1，此時處理完這個條件下的程式碼後就應該將其彈出了，如下圖：

從上圖中我們會看到每一步的呼叫情況，尤其是對funDiGui函式自身的呼叫，這裡強調一點是函式funDiGui在呼叫的時候，其中使用的變數x只歸屬於當前所在的函式本身，即每個函式只能使用自己的引數，在一個函式的呼叫中不能訪問另一函式的變數x。

以上就是遞迴函式呼叫棧的使用。但要注意因為是存在棧中，如果遞迴次數過多，這些函式資訊會佔用大量的記憶體，棧越高，存的函式資訊就越多，記憶體佔用就越多。此時就要考慮用普通迴圈代替遞迴了，或者使用一種叫尾遞迴的方式。下面簡單介紹下尾遞迴。

4 尾遞迴

特點：

遞迴呼叫是整個函式體中最後執行的語句，即呼叫函式本身的程式碼在最後遞迴呼叫函式的返回值不作為表示式的一部分，即返回值不能再去和上一層函式的引數有操作關係

比如我們上面介紹的階乘，最後程式碼是return x * funDiGui(x-1) ，但每次遞迴呼叫的函式的返回值要作為表示式的一部分去乘以上一層函式的引數x，這就不是尾遞迴。

尾遞迴中呼叫的遞迴函式返回值不能參與上一層表示式的計算。那麼在階乘中，n*(n-1)這樣的表示式中，(n-1)就是呼叫的遞迴函式的返回值，如何才能使其不參與表示式的操作呢？方法就是再定義一個初始值為1的變數a，a來維護遞迴層次的深度，同時在每層中將其和n進行相乘作為下一層的引數a，最後將a返回即可。程式碼如下：

def funDiGui(x,a): if x == 1: //基線條件 return a else: return funDiGui(x-1,x*a) //遞迴條件

上面程式碼a的初始值為1，a在表示每層的同時，將當前層的x和a相乘作為下一層的引數a，這樣就表達出了連續相乘的邏輯。這樣也就不必將上一個呼叫的遞迴函式的返回值進行儲存，因為最後一個值a就是結果。在一些編譯器中，就是利用這個原理，棧中不再儲存每次呼叫的返回值狀態，編譯器判斷出是尾遞迴後會覆蓋當前活動的記錄，而不是像呼叫棧中在上面加上一個新的，這樣就使棧的使用空間大大減小，執行效率自然也會提高。

一句話，迴圈呼叫本身的方式或方法就是遞迴。當然如果無跳出的遞迴，那就是死迴圈了，會把伺服器幹掉。不論用什麼程式語言都是很容易實現的，寫一個方法，然後在這個方法體中再呼叫這個方法。