開始之前，首先來看一個通常我們不會以遞歸的形式思考的問題。假設我們想計算整數n的階乘。n的階乘可寫作n!，其結果是1~n之間的各數之積。比如，4！=4×3×2×1。一種計算法方法是循環遍歷其中的每一個數，然后與它之前的數相乘作為結果再參與下一次計算。這種方法稱為迭代法，可以正式定義為：
n! = (n)(n - 1)(n - 2) . . . (1)
看待這個問題的另一種方式是將n!定義為更小的階乘形式。為了實現這一步，我們將n!定義為n-1階乘的n倍。當然，求解（n-1）!的過程同n!一樣，只是變小了一些。如果我們再把（n-1）!看做n-1倍的（n-2）!，（n-2）!看做n-2倍的（n-3）!，一直到n=1時，我們就計算完了。這就是遞歸的方式，可以正式定義為：
圖3-1展示了利用遞歸的方法計算的4!過程。它也勾畫出了遞歸過程中的兩個基本階段：遞推與回歸。在遞推階段，每一個遞歸調用通過進一步調用自己來記住這次遞歸過程。當其中有調用滿足終止條件時，遞推結束。比如，在計算n的階乘時，終止條件是當n=1和n=0，此時函數只須簡單地返回1即可。每一個遞歸函數都必須擁有至少一個終止條件；否則，遞推階段就永遠不會結束了。一旦遞推階段結束，處理過程就進入回歸階段，在這之前的函數調用以逆序的方式回歸，直到最初調用的函數返回為止，此時遞歸過程結束。
Figure 3.1. Computing 4! recursively
示例3-1展示了一個C函數fact，它接受一個整數n作為參數，以遞歸的方式計算n的階乘。該函數按照如下的方式工作：如果n小于0，該函數直接返回0，這代表一個錯誤。如果n等于0或者1，該函數返回1，這是因為o!和1!都等于1，以上就是終止遞歸的條件。否則，函數返回n-1的階乘的n倍。而n-1的階乘又會以遞歸的方式再次調用fact來計算，如此繼續。注意觀察遞歸實現與我們之前對遞歸的定義之間的相同點。
Example 3.1. Implementation of a Function for Computing Factorials Recursively
int fact(int n) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return 1;
else
return n * fact(n - 1);
}
為了理解遞歸究竟是如何工作的，有必要先看看C語言中函數的執行方式。基于這點，我們需要了解一點關于C程序在內存中的組織方式。基本上來說一個可執行程序由4個區域組成：代碼段、靜態數據區、堆與棧（見圖3-2a）。代碼段包含程序運行時所執行的機器指令。靜態數據區包含在程序生命周期內一直持久的數據，比如全局變量和靜態局部變量。堆包含程序運行時動態分配的存儲空間，比如用malloc分配的內存。棧包含函數調用的信息。按照慣例，堆的增長方向為從程序低地址到高地址向上增長，而棧的增長方向剛好相反（實際情況可能不是這樣，與CPU的體系結構有關）。
當C程序中調用了一個函數時，棧中會分配一塊空間來保存與這個調用相關的信息。每一個調用都被當做是活躍的。棧上的那塊存儲空間稱為活躍記錄，或者稱為棧幀。棧幀由5個區域組成：輸入參數、返回值空間、計算表達式時用到的臨時存儲空間、函數調用時保存的狀態信息以及輸出參數（見圖3-2b）。輸入參數是傳遞到活躍記錄中的參數；輸出參數是傳遞給在活躍記錄中調用的函數所使用的。一個活躍記錄中的輸出參數就成為棧中下一個活躍記錄的輸入參數。函數調用產生的活躍記錄將一直存在于棧中直到這個函數調用結束。
回到示例3-1，考慮一下當計算4!時棧中都發生了些什么。初始調用fact會在棧中產生一個活躍記錄，輸入參數n=4（見圖3-3，第1步）。由于這個調用沒有滿足函數的終止條件，因此fact將繼續以n=3為參數遞歸調用。這將在棧上創建另一個活躍記錄，但這次輸入參數（見圖3-3，第2步）。這里，n=3也是第一個活躍期中的輸出參數，因為正是在第一個活躍期內調用fact產生了第二個活躍期。這個過程將一直繼續，直到n的值變為1，此時滿足終止條件，fact將返回1（見圖3-3，第4步）。
Figure 3.2. The organization in memory of (a) a C program and (b) an activation record
Figure 3.3. The stack of a C program while computing 4! recursively
一旦當n=1時的活躍期結束，n=2時的遞歸計算結果就是2×1=2，因而n=2時的活躍期也將結束，返回值為2（見圖3-3，第5步）。結果就是n=3時的遞歸計算結果表示為3×2=6，因此n=3時的活躍期結束，返回值為6（見圖3-3，第6步）。最終，當n=4時的遞歸計算結果將表示為6×4=24，n=4時的活躍期將結束，返回值為24（見圖3-3，第7步）。此時，函數已經從最初的調用中返回，遞歸過程結束。
棧是用來存儲函數調用信息的絕好方案，這正是由于其后進先出的特點（見第6章）精確滿足了函數調用和返回的順序。然而，使用棧也有一些缺點。棧維護了每個函數調用的信息直到函數返回后才釋放，這需要占用相當大的空間，尤其是在程序中使用了許多遞歸調用的情況下。除此之外，因為有大量的信息需要保存和恢復，因此生成和銷毀活躍記錄需要耗費一定的時間。如此一來當函數調用的開銷變得很大時，我們就需要考慮應該采用迭代的方案。幸運的是，我們可以采用一種稱為尾遞歸的特殊遞歸方式來避免前面提到的這些缺點。
