尾遞歸

尾遞歸定義：

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

原理

當編譯器檢測到一個函數調用是尾遞歸的時候，它就覆寫目前的活躍記錄而不是在棧中去建立一個新的。編譯器可以做到這點，因為遞歸調用是目前活躍期内最後一條待執行的語句，于是當這個調用傳回時棧幀中并沒有其他事情可做，是以也就沒有儲存棧幀的必要了。通過覆寫目前的棧幀而不是在其之上重新添加一個，這樣所使用的棧空間就大大縮減了，這使得實際的運作效率會變得更高。是以，隻要有可能我們就需要将遞歸函數寫成尾遞歸的形式

執行個體

為了了解尾遞歸是如何工作的，讓我們再次以遞歸的形式計算階乘。首先，這可以很容易讓我們了解為什麼之前所定義的遞歸不是尾遞歸。回憶之前對計算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很相似。讀者可以注意一下函數的具體實作和尾遞歸定義的相似之處。

示例3-2：以尾遞歸的形式計算階乘的一個函數實作[1]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

<code>/* facttail.c */</code>

<code>#include "facttail.h"</code>

<code>/* facttail  */</code>

<code>int</code>

<code>facttail(</code><code>int</code>

<code>n,</code><code>int</code>

<code>a)</code>

<code>{</code>

<code>    </code><code>/* Compute a factorial in a tail-recursive manner. */</code>

<code>    </code><code>if</code>

<code>(n &lt; 0)</code>

<code>        </code><code>return</code>

<code>0;</code>

<code>    </code><code>else</code>

<code>if</code> <code>(n == 0)</code>

<code>1;</code>

<code>if</code> <code>(n == 1)</code>

<code>a;</code>

<code>facttail(n - 1, n * a);</code>

<code>}</code>

示例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)); 這樣則隻保留後一個函數堆棧即可，之前的可優化删去。

也許在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)

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

調用都使得調用鍊條不斷加長. 系統不得不使用棧進行資料儲存和恢複.而尾遞歸就

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

具體事例2 快速排序算法實施尾遞歸優化

void quickSort(SqList * list , int low ,int high)

{

int pivot;

while(low&lt;high)

pivot=Partition(list,low,high);

quickSort(list, low,pivot - 1);

//quickSort(list,low,pivot-1); 原遞歸調用

//quickSort(list,pivot+1,high);

low = pivot+1; /*尾遞歸*/

//

首先：尾遞歸是線性遞歸的子集，屬于線性遞歸。具體概念請參閱各大高校出版的書籍。作者把概念搞錯了

其次，上文所舉的第二個例子中在TailRescuvie(n-1, 1)沒有計算出來之前，是不能return的。也就是說遞歸過程和第一個例子是差不多的，根本沒有節約資源，甚至更浪費。

其實，編譯器會很容易的對尾遞歸使用跳轉語句進行優化，其實是可以return的。

尾遞歸就是把目前的運算結果（或路徑）放在參數裡傳給下層函數，深層函數所面對的不是越來越簡單的問題，而是越來越複雜的問題——因為參數裡帶有前面若幹步的運算路徑。對于階乘而言，越深并不意味着越複雜。

從時間和空間效率上看，尾遞歸和傳統遞歸差不多。遞歸運算效率低主要是分支巨大，像階乘這類單分支的遞歸，效率并不低。遞歸運算的深度和運算總量大緻成指數關系，return多次并不會造成顯著的性能損失。

一言以蔽之，傳統遞歸越深，距離目标越近；尾遞歸越深，距離起點越遠。

尾遞歸适用于運算對目前遞歸路徑有依賴的問題，傳統遞歸适用于運算對更深層遞歸有依賴的問題。

/**************************************************************************************************/

第二作者對第二個例子的解釋上有點不全面，尾遞歸的效果就是去除了将下層的結果再次傳回給上層，需要上層繼續計算才得出結果的弊端，如果讀者仔細觀看第二例子就可以看出，其實每個遞歸的結果是存儲在第二個參數a中的，到最後一次計算的時候，會隻傳回一個a的值，但是因為是遞歸的原理雖然仍然要傳回給上層，依次到頂部才給出結果，但是不需要再做計算了，這點的好處就是每次配置設定的記憶體不會因為遞歸而擴大。

在效率上，兩者的确差不多。