-
尾遞歸
鎖定
- 中文名
- 尾遞歸
- 檢測到時
- 它就覆蓋當前的活動記錄
- 而不是
- 在棧中去創建一個新的
- 編譯器
- 可以做到這點
尾遞歸原理
當編譯器檢測到一個函數調用是尾遞歸的時候，它就覆蓋當前的活動記錄而不是在棧中去創建一個新的。編譯器可以做到這點，因為遞歸調用是當前活躍期內最後一條待執行的語句，於是當這個調用返回時棧幀中並沒有其他事情可做，因此也就沒有保存棧幀的必要了。通過覆蓋當前的棧幀而不是在其之上重新添加一個，這樣所使用的棧空間就大大縮減了，這使得實際的運行效率會變得更高。
尾遞歸實例
為了理解尾遞歸是如何工作的，讓我們再次以遞歸的形式計算階乘。首先，這可以很容易讓我們理解為什麼之前所定義的遞歸不是尾遞歸。回憶之前對計算n!的定義：在每個活躍期計算n倍的(n－1)!的值，讓n=n－1並持續這個過程直到n=1為止。這種定義不是尾遞歸的，因為每個活躍期的返回值都依賴於用n乘以下一個活躍期的返回值，因此每次調用產生的棧幀將不得不保存在棧上直到下一個子調用的返回值確定。現在讓我們考慮以尾遞歸的形式來定義計算n!的過
[1]
程。
這種定義還需要接受第二個參數a，除此之外並沒有太大區別。a（初始化為1）維護遞歸層次的深度。這就讓我們避免了每次還需要將返回值再乘以n。然而，在每次遞歸調用中，令a=na並且n=n－1。繼續遞歸調用，直到n=1，這滿足結束條件，此時直接返回a即可。
代碼實例3-2給出了一個C函數facttail，它接受一個整數n並以尾遞歸的形式計算n的階乘。這個函數還接受一個參數a，a的初始值為1。facttail使用a來維護遞歸層次的深度，除此之外它和fact很相似。讀者可以注意一下函數的具體實現和尾遞歸定義的相似之處。
/*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的調用，但這並不是必需的。換句話説，在遞歸調用之後還可以有其他的語句執行，只是它們只能在遞歸調用沒有執行時才可以執行
[1]
。
尾遞歸是極其重要的，不用尾遞歸，函數的堆棧耗用難以估量，需要保存很多中間函數的堆棧。比如f(n, sum) = f(n-1) + value(n) + sum; 會保存n個函數調用堆棧，而使用尾遞歸f(n, sum) = f(n-1, sum+value(n)); 這樣則只保留後一個函數堆棧即可，之前的可優化刪去。
原文的説法是錯誤的：原文如下：
一種算法, 用於計算機編程技術.
尾遞歸是針對傳統的遞歸算法而言的, 傳統的遞歸算法在很多時候被視為洪水猛獸. 它的名聲狼籍, 好像永遠和低效聯繫在一起.
尾遞歸就是從最後開始計算, 每遞歸一次就算出相應的結果, 也就是説, 函數調用出現在調用者函數的尾部, 因為是尾部, 所以根本沒有必要去保存任何局部變量. 直接讓被調用的函數返回時越過調用者, 返回到調用者的調用者去.
以下是具體實例:
線性遞歸:
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保存.
- 參考資料
-
- 1. 尾遞歸 ．51CTO.COM．2012-12-06[引用日期2013-06-03]
