開(kāi)始之前，首先來(lái)看一個(gè)通常我們不會(huì)以遞歸的形式思考的問(wèn)題。假設(shè)我們想計(jì)算整數(shù)n的階乘。n的階乘可寫作n!，其結(jié)果是1~n之間的各數(shù)之積。比如，4！=4×3×2×1。一種計(jì)算法方法是循環(huán)遍歷其中的每一個(gè)數(shù)，然后與它之前的數(shù)相乘作為結(jié)果再參與下一次計(jì)算。這種方法稱為迭代法，可以正式定義為：
n! = (n)(n - 1)(n - 2) . . . (1)看待這個(gè)問(wèn)題的另一種方式是將n!定義為更小的階乘形式。為了實(shí)現(xiàn)這一步，我們將n!定義為n-1階乘的n倍。當(dāng)然，求解（n-1）!的過(guò)程同n!一樣，只是變小了一些。如果我們?cè)侔眩╪-1）!看做n-1倍的（n-2）!，（n-2）!看做n-2倍的（n-3）!，一直到n=1時(shí)，我們就計(jì)算完了。這就是遞歸的方式，可以正式定義為：
圖3-1展示了利用遞歸的方法計(jì)算的4!過(guò)程。它也勾畫出了遞歸過(guò)程中的兩個(gè)基本階段：遞推與回歸。在遞推階段，每一個(gè)遞歸調(diào)用通過(guò)進(jìn)一步調(diào)用自己來(lái)記住這次遞歸過(guò)程。當(dāng)其中有調(diào)用滿足終止條件時(shí)，遞推結(jié)束。比如，在計(jì)算n的階乘時(shí)，終止條件是當(dāng)n=1和n=0，此時(shí)函數(shù)只須簡(jiǎn)單地返回1即可。每一個(gè)遞歸函數(shù)都必須擁有至少一個(gè)終止條件；否則，遞推階段就永遠(yuǎn)不會(huì)結(jié)束了。一旦遞推階段結(jié)束，處理過(guò)程就進(jìn)入回歸階段，在這之前的函數(shù)調(diào)用以逆序的方式回歸，直到最初調(diào)用的函數(shù)返回為止，此時(shí)遞歸過(guò)程結(jié)束。
Figure 3.1. Computing 4! recursively
示例3-1展示了一個(gè)C函數(shù)fact，它接受一個(gè)整數(shù)n作為參數(shù)，以遞歸的方式計(jì)算n的階乘。該函數(shù)按照如下的方式工作：如果n小于0，該函數(shù)直接返回0，這代表一個(gè)錯(cuò)誤。如果n等于0或者1，該函數(shù)返回1，這是因?yàn)閛!和1!都等于1，以上就是終止遞歸的條件。否則，函數(shù)返回n-1的階乘的n倍。而n-1的階乘又會(huì)以遞歸的方式再次調(diào)用fact來(lái)計(jì)算，如此繼續(xù)。注意觀察遞歸實(shí)現(xiàn)與我們之前對(duì)遞歸的定義之間的相同點(diǎn)。
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語(yǔ)言中函數(shù)的執(zhí)行方式。基于這點(diǎn)，我們需要了解一點(diǎn)關(guān)于C程序在內(nèi)存中的組織方式。基本上來(lái)說(shuō)一個(gè)可執(zhí)行程序由4個(gè)區(qū)域組成：代碼段、靜態(tài)數(shù)據(jù)區(qū)、堆與棧（見(jiàn)圖3-2a）。代碼段包含程序運(yùn)行時(shí)所執(zhí)行的機(jī)器指令。靜態(tài)數(shù)據(jù)區(qū)包含在程序生命周期內(nèi)一直持久的數(shù)據(jù)，比如全局變量和靜態(tài)局部變量。堆包含程序運(yùn)行時(shí)動(dòng)態(tài)分配的存儲(chǔ)空間，比如用malloc分配的內(nèi)存。棧包含函數(shù)調(diào)用的信息。按照慣例，堆的增長(zhǎng)方向?yàn)閺某绦虻偷刂返礁叩刂废蛏显鲩L(zhǎng)，而棧的增長(zhǎng)方向剛好相反（實(shí)際情況可能不是這樣，與CPU的體系結(jié)構(gòu)有關(guān)）。
當(dāng)C程序中調(diào)用了一個(gè)函數(shù)時(shí)，棧中會(huì)分配一塊空間來(lái)保存與這個(gè)調(diào)用相關(guān)的信息。每一個(gè)調(diào)用都被當(dāng)做是活躍的。棧上的那塊存儲(chǔ)空間稱為活躍記錄，或者稱為棧幀。棧幀由5個(gè)區(qū)域組成：輸入?yún)?shù)、返回值空間、計(jì)算表達(dá)式時(shí)用到的臨時(shí)存儲(chǔ)空間、函數(shù)調(diào)用時(shí)保存的狀態(tài)信息以及輸出參數(shù)（見(jiàn)圖3-2b）。輸入?yún)?shù)是傳遞到活躍記錄中的參數(shù)；輸出參數(shù)是傳遞給在活躍記錄中調(diào)用的函數(shù)所使用的。一個(gè)活躍記錄中的輸出參數(shù)就成為棧中下一個(gè)活躍記錄的輸入?yún)?shù)。函數(shù)調(diào)用產(chǎn)生的活躍記錄將一直存在于棧中直到這個(gè)函數(shù)調(diào)用結(jié)束。
回到示例3-1，考慮一下當(dāng)計(jì)算4!時(shí)棧中都發(fā)生了些什么。初始調(diào)用fact會(huì)在棧中產(chǎn)生一個(gè)活躍記錄，輸入?yún)?shù)n=4（見(jiàn)圖3-3，第1步）。由于這個(gè)調(diào)用沒(méi)有滿足函數(shù)的終止條件，因此fact將繼續(xù)以n=3為參數(shù)遞歸調(diào)用。這將在棧上創(chuàng)建另一個(gè)活躍記錄，但這次輸入?yún)?shù)（見(jiàn)圖3-3，第2步）。這里，n=3也是第一個(gè)活躍期中的輸出參數(shù)，因?yàn)檎窃诘谝粋€(gè)活躍期內(nèi)調(diào)用fact產(chǎn)生了第二個(gè)活躍期。這個(gè)過(guò)程將一直繼續(xù)，直到n的值變?yōu)?，此時(shí)滿足終止條件，fact將返回1（見(jiàn)圖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
一旦當(dāng)n=1時(shí)的活躍期結(jié)束，n=2時(shí)的遞歸計(jì)算結(jié)果就是2×1=2，因而n=2時(shí)的活躍期也將結(jié)束，返回值為2（見(jiàn)圖3-3，第5步）。結(jié)果就是n=3時(shí)的遞歸計(jì)算結(jié)果表示為3×2=6，因此n=3時(shí)的活躍期結(jié)束，返回值為6（見(jiàn)圖3-3，第6步）。最終，當(dāng)n=4時(shí)的遞歸計(jì)算結(jié)果將表示為6×4=24，n=4時(shí)的活躍期將結(jié)束，返回值為24（見(jiàn)圖3-3，第7步）。此時(shí)，函數(shù)已經(jīng)從最初的調(diào)用中返回，遞歸過(guò)程結(jié)束。
棧是用來(lái)存儲(chǔ)函數(shù)調(diào)用信息的絕好方案，這正是由于其后進(jìn)先出的特點(diǎn)（見(jiàn)第6章）精確滿足了函數(shù)調(diào)用和返回的順序。然而，使用棧也有一些缺點(diǎn)。棧維護(hù)了每個(gè)函數(shù)調(diào)用的信息直到函數(shù)返回后才釋放，這需要占用相當(dāng)大的空間，尤其是在程序中使用了許多遞歸調(diào)用的情況下。除此之外，因?yàn)橛写罅康男畔⑿枰４婧突謴?fù)，因此生成和銷毀活躍記錄需要耗費(fèi)一定的時(shí)間。如此一來(lái)當(dāng)函數(shù)調(diào)用的開(kāi)銷變得很大時(shí)，我們就需要考慮應(yīng)該采用迭代的方案。幸運(yùn)的是，我們可以采用一種稱為尾遞歸的特殊遞歸方式來(lái)避免前面提到的這些缺點(diǎn)。
