計算機專業本科的朋友在大二的專業課《數據結構》裡想必都學過“遞歸”的概念。但是教材裡並沒有提到尾遞歸。而很多朋友在找程序員這份工作時，經常被面試官問起什麼是尾遞歸。今天我們就說一說吧。
如果一個函數中所有遞歸形式的調用都出現在函數的末尾，則該遞歸函數是尾遞歸的。為什麼我們會強調尾遞歸？因為大多數現代的編譯器會針對尾遞歸自動進行代碼優化。
可能您還是覺得抽象，咱們來看個具體的例子。
新建一個txt文件，把下列代碼拷貝進去，另存為html，用瀏覽器打開。
您會看到一前一後兩個彈出窗口，內容都為10的階乘。
其中第二個函數factorial2，就稱之為尾遞歸函數。
我們先看普通的遞歸函數factorial，和《數據結構》教科書上的沒有區別。
跟著我調試一下階乘的計算，加深遞歸過程中的堆棧操作。
為簡單起見，我們計算5的階乘就夠了。輸入參數n為5。執行到第七行，5的階乘等於5乘以4的階乘。單步調試進去：
注意看下圖的Call Stack列表，此時我們已經有兩個factorial函數的棧幀了。什麼是棧幀？複習一下大學計算機原理學到的知識：因為在函數執行中，每一個函數調用都會把當前函數的調用位置和內部變量保存在棧裡面，稱為一個棧幀（Stack Frame）。
其中最下面的保存了n=5的計算上下文，最頂層的代表當前棧幀，即n=4的計算上下文。
因為我們還是不知道4的階乘到底是多少，所以到第7行的時候再調試進去。
多了一個n=3的棧幀：
n=2的棧幀：
終於我們來到了n=1的情況。看下圖Call Stack裡的棧幀列表，最頂層的代表當前n=1的計算上下文。此時我們已經知道n=1的階乘如何計算了，就為1本身。此時執行到了第五行，返回1的階乘的計算結果：1。注意，這行語句返回之後，當前的棧幀就會被銷燬，我們就要回到下一層n=2的棧幀去啦。
看下圖，此時只剩4個棧幀了，最頂層代表n=2的棧幀。因為現在1的階乘結果已經出來了，所以2的階乘結果也能計算了，為2乘以1.
2的階乘返回後，現在只剩3個棧幀，最頂層為n=3的計算上下文。3的階乘也能計算了，為3乘以上個棧幀返回的計算結果，即2的階乘結果，所以最後為3× 2 = 6。
4的階乘計算，只剩兩個棧幀。
5的計算結果，回到最初最先被壓到堆棧底部的n=5的棧幀。計算完畢。
是不是體會到了教科書上關於棧“先進後出”的思想？
好了，再來看看用尾遞歸實現的階乘。
5的階乘入口，調用另一個函數tailFactorial，注意第20行第二個輸入參數1，這個參數用於存儲當前階乘的計算結果。
遞歸調用自身，因為不知道5的階乘怎麼算，但是因為上面提到過，這個尾遞歸函數的第二個參數實際上存放的就是當前輸入參數為n時的階乘計算結果。尾遞歸的結束條件就是，當n為1時，返回這個階乘計算結果。當n大於1時，首先將n和當前的階乘計算結果相乘，結果作為輸入參數傳到遞歸調用的下一個棧幀中去。同時，因為當前參數n已經計算了一次乘法，因此我們需要把n減一。於是，才有了本文中尾遞歸函數的這個代碼實現。
現在我們來到了tailFactorial的棧幀，
n = 3，此時total為 5 × 4 = 20，由於遞歸的緣故，已經有兩個tailFactorial的棧幀了。
n = 2， total = 60，3個tailFactorial的棧幀。
n = 1，total = 120，計算結束啦！
注意看Jerry上面的這幾個圖裡，tailFactorial都標註成"useless（無用）"。為什麼呢？因為按照尾遞歸的階乘計算公式，當前階乘的計算結果已經通過第二個參數total保存了起來，因此沒有必要再用一個棧幀去保存當前的計算上下文了。因此對於現代編譯器，一旦檢測到函數是尾調用調用後，編譯器會進行代碼優化，所以不再需要使用額外的棧幀保留每次遞歸調用記錄，因為調用位置、中間計算結果，內部局部變量等信息都不再需要了。這就是所謂的“尾遞歸優化”可以有效防止棧溢出（stack overflow）。
大家可以把我上面代碼的N改為20，比較用普通階乘遞歸函數和用尾遞歸函數計算20的階乘，發現性能有巨大差異：前者需要10毫秒，後者僅需不到1毫秒！
希望這26行代碼能幫助大家理解尾遞歸和尾遞歸優化，在將來面試官問到這個話題時能從容應答。
閱讀更多 汪子熙SAP 的文章
