在計算機科學領域中，遞歸式通過遞歸函數來實現的。程序調用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。
一般來說，遞歸需要有：邊界條件、遞歸前進段和遞歸返回段。
當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數裡調用自身；
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
本文地址：http://www.cnblogs.com/archimedes/p/rescuvie-tailrescuvie.html，轉載請注明源地址。
問題：計算n！
數學上的計算公式為：n！=n×(n-1)×(n-2)……2×1
使用遞歸的方式，可以定義為：
以遞歸的方式計算4！
F(4)=4×F(3) 遞歸階段
F(3)=3×F(2)
F(2)=2×F(1)
F(1)=1 終止條件
F(2)=(2)×(1) 回歸階段
F(3)=(3)×(2)
F(4)=(4)×(6)
24 遞歸完成
以遞歸方式實現階乘函數的實現：
int fact(int n) {
if(n < 0)
return 0;
else if (n == 0 || n == 1)
return 1;
else
return n * fact(n - 1);
}
下面來詳細分析遞歸的工作原理
先看看C語言中函數的執行方式，需要了解一些關於C程序在內存中的組織方式，基本上來說一個可執行程序由4個區域組成：代碼段、靜態數據區、堆、棧
代碼段：包含程序運行時所執行的機器指令。
靜態數據區：包含在程序生命周期內一直持久的數據。e.g 全局變量和靜態局部變量
堆：包含程序運行時動態分配的存儲空間。e.g 用malloc分配的內存
棧：包含函數調用信息。
堆的增長方向為從低地址到高地址向上增長，而棧的增長方向剛好相反（實際情況與CPU的體系結構有關）
當C程序中調用了一個函數時，棧中會分配一塊空間來保存與這個調用相關的信息，每一個調用都被當作是活躍的。棧上的那塊存儲空間稱為活躍記錄或者棧幀
棧幀由5個區域組成：輸入參數、返回值空間、計算表達式時用到的臨時存儲空間、函數調用時保存的狀態信息以及輸出參數，參見下圖：
棧是用來存儲函數調用信息的絕好方案，然而棧也有一些缺點：
棧維護了每個函數調用的信息直到函數返回後才釋放，這需要占用相當大的空間，尤其是在程序中使用了許多的遞歸調用的情況下。除此之外，因為有大量的信息需要保存和恢復，因此生成和銷毀活躍記錄需要消耗一定的時間。我們需要考慮采用迭代的方案。幸運的是我們可以采用一種稱為尾遞歸的特殊遞歸方式來避免前面提到的這些缺點。
如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最後執行的語句且它的返回值不屬於表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。
當編譯器檢測到一個函數調用是尾遞歸的時候，它就覆蓋當前的活動記錄而不是在棧中去創建一個新的。編譯器可以做到這點，因為遞歸調用是當前活躍期內最後一條待執行的語句，於是當這個調用返回時棧幀中並沒有其他事情可做，因此也就沒有保存棧幀的必要了。通過覆蓋當前的棧幀而不是在其之上重新添加一個，這樣所使用的棧空間就大大縮減了，這使得實際的運行效率會變得更高。雖然編譯器能夠優化尾遞歸造成的棧溢出問題，但是在編程中，我們還是應該盡量避免尾遞歸的出現，因為所有的尾遞歸都是可以用簡單的goto循環替代的。
為了理解尾遞歸是如何工作的，讓我們再次以遞歸的形式計算階乘。首先，這可以很容易讓我們理解為什麼之前所定義的遞歸不是尾遞歸。回憶之前對計算n!的定義：在每個活躍期計算n倍的(n－1)!的值，讓n=n－1並持續這個過程直到n=1為止。這種定義不是尾遞歸的，因為每個活躍期的返回值都依賴於用n乘以下一個活躍期的返回值，因此每次調用產生的棧幀將不得不保存在棧上直到下一個子調用的返回值確定。現在讓我們考慮以尾遞歸的形式來定義計算n!的過程。
這種定義還需要接受第二個參數a，除此之外並沒有太大區別。a（初始化為1）維護遞歸層次的深度。這就讓我們避免了每次還需要將返回值再乘以n。然而，在每次遞歸調用中，令a=na並且n=n－1。繼續遞歸調用，直到n=1，這滿足結束條件，此時直接返回a即可。
代碼實例給出了一個C函數facttail，它接受一個整數n並以尾遞歸的形式計算n!。這個函數還接受一個參數a，a的初始值為1。facttail使用a來維護遞歸層次的深度，除此之外它和fact很相似。讀者可以注意一下函數的具體實現和尾遞歸定義的相似之處。
int facttail(int n, int a)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}
示例中的函數是尾遞歸的，因為對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中（亦是棧語言），如果想要保持語言的高並發特性，就必須用尾遞歸來替代傳統的遞歸。
