尾遞歸

如果一個函式中所有遞歸形式的調用都出現在函式的末尾，我們稱這個遞歸函式是尾遞歸的。當遞歸調用是整個函式體中最後執行的語句且它的返回值不屬於表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函式的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成最佳化的代碼。

基本介紹

• 中文名：尾遞歸
• 檢測到時：它就覆蓋當前的活動記錄
• 而不是：在棧中去創建一個新的
• 編譯器：可以做到這點

原理

當編譯器檢測到一個函式調用是尾遞歸的時候，它就覆蓋當前的活動記錄而不是在棧中去創建一個新的。編譯器可以做到這點，因為遞歸調用是當前活躍期內最後一條待執行的語句，於是當這個調用返回時棧幀中並沒有其他事情可做，因此也就沒有保存棧幀的必要了。通過覆蓋當前的棧幀而不是在其之上重新添加一個，這樣所使用的棧空間就大大縮減了，這使得實際的運行效率會變得更高。

實例

為了理解尾遞歸是如何工作的，讓我們再次以遞歸的形式計算階乘。首先，這可以很容易讓我們理解為什麼之前所定義的遞歸不是尾遞歸。回憶之前對計算n!的定義：在每個活躍期計算n倍的(n－1)!的值，讓n=n－1並持續這個過程直到n=1為止。這種定義不是尾遞歸的，因為每個活躍期的返回值都依賴於用n乘以下一個活躍期的返回值，因此每次調用產生的棧幀將不得不保存在棧上直到下一個子調用的返回值確定。現在讓我們考慮以尾遞歸的形式來定義計算n!的過程。

這種定義還需要接受第二個參數a，除此之外並沒有太大區別。a（初始化為1）維護遞歸層次的深度。這就讓我們避免了每次還需要將返回值再乘以n。然而，在每次遞歸調用中，令a=na並且n=n－1。繼續遞歸調用，直到n=1，這滿足結束條件，此時直接返回a即可。

代碼實例3-2給出了一個C函式facttail，它接受一個整數n並以尾遞歸的形式計算n的階乘。這個函式還接受一個參數a，a的初始值為1。facttail使用a來維護遞歸層次的深度，除此之外它和fact很相似。讀者可以注意一下函式的具體實現和尾遞歸定義的相似之處。

示例3-2：以尾遞歸的形式計算階乘的一個函式實現

/*facttail.c*/#include"facttail.h"/*facttail*/int facttail(int n, int a){    /*Compute a factorialina tail - recursive manner.*/        if (n < 0)        return 0;        else if (n == 0)        return 1;        else if (n == 1)        return a;    else        return facttail(n - 1, n * a);}

示例3-2中的函式是尾遞歸的，因為對facttail的單次遞歸調用是函式返回前最後執行的一條語句。在facttail中碰巧最後一條語句也是對facttail的調用，但這並不是必需的。換句話說，在遞歸調用之後還可以有其他的語句執行，只是它們只能在遞歸調用沒有執行時才可以執行。

尾遞歸是極其重要的，不用尾遞歸，函式的堆疊耗用難以估量，需要保存很多中間函式的堆疊。比如f(n, sum) = f(n-1) + value(n) + sum; 會保存n個函式調用堆疊，而使用尾遞歸f(n, sum) = f(n-1, sum+value(n)); 這樣則只保留後一個函式堆疊即可，之前的可最佳化刪去。

也許在C語言中有很多的特例，但程式語言不只有C語言，在函式式語言Erlang中（亦是棧語言），如果想要保持語言的高並發特性，就必須用尾遞歸來替代傳統的遞歸。

原文的說法是錯誤的：原文如下：

一種算法, 用於計算機編程技術.

尾遞歸是針對傳統的遞歸算法而言的, 傳統的遞歸算法在很多時候被視為洪水猛獸. 它的名聲狼籍, 好像永遠和低效聯繫在一起.

尾遞歸就是從最後開始計算, 每遞歸一次就算出相應的結果, 也就是說, 函式調用出現在調用者函式的尾部, 因為是尾部, 所以根本沒有必要去保存任何局部變數. 直接讓被調用的函式返回時越過調用者, 返回到調用者的調用者去.

以下是具體實例:

線性遞歸:

long Rescuvie(long n) {    return (n == 1) ? 1 : n * Rescuvie(n - 1);}

尾遞歸:

long TailRescuvie(long n, long a) {    return (n == 1) ? a : TailRescuvie(n - 1, a * n);}long TailRescuvie(long n) {//封裝用的        return (n == 0) ? 1 : TailRescuvie(n, 1);}

當n = 5時

對於線性遞歸, 他的遞歸過程如下:

Rescuvie(5)

{5 * Rescuvie(4)}

{5 * {4 * Rescuvie(3)}}

{5 * {4 * {3 * Rescuvie(2)}}}

{5 * {4 * {3 * {2 * Rescuvie(1)}}}}

{5 * {4 * {3 * {2 * 1}}}}

{5 * {4 * {3 * 2}}}

{5 * {4 * 6}}

{5 * 24}

120

對於尾遞歸, 他的遞歸過程如下:

TailRescuvie(5)

TailRescuvie(5, 1)

TailRescuvie(4, 5)

TailRescuvie(3, 20)

TailRescuvie(2, 60)

TailRescuvie(1, 120)

120

很容易看出, 普通的線性遞歸比尾遞歸更加消耗資源, 在實現上說, 每次重複的過程

調用都使得調用鏈條不斷加長. 系統不得不使用棧進行數據保存和恢復.而尾遞歸就

不存在這樣的問題, 因為他的狀態完全由n和a保存.