基本遞歸

遞歸有兩個階段：遞推與回歸。

遞推：在遞推階段每一個遞歸調(diào)用通過進一步調(diào)用自己來記住這次遞歸過程。當其中有調(diào)用滿足終止條件時，遞推結(jié)束。

回歸：函數(shù)調(diào)用已逆序的方式回歸，直到最初調(diào)用的函數(shù)返回為止，此時遞歸過程結(jié)束。

基本上來說，一個程序由4個區(qū)域組成：代碼段、靜態(tài)數(shù)據(jù)區(qū)、堆與棧。代碼段包含程序運行時所執(zhí)行的機器指令。靜態(tài)數(shù)據(jù)區(qū)包含在程序生命周期都一直存在的數(shù)據(jù)，不如全局變量和靜態(tài)局部變量。堆包含程序運行時動態(tài)分配的空間，比如malloc。棧包含函數(shù)調(diào)用的信息。如下圖所示：

下面是一個使用遞歸計算階乘的例子：

尾遞歸

為了解決普通遞歸需要相當大的空間來保存函數(shù)信息，提出了尾遞歸的遞歸方式。

當遞歸調(diào)用是整個函數(shù)中最后執(zhí)行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調(diào)用就是尾遞歸的。

當編譯器檢查到一個函數(shù)是尾遞歸的時候，它就會覆蓋當前活躍記錄而不是在棧中去創(chuàng)建一個新的，這樣就解決了普通遞歸函數(shù)占用棧空間過大的問題。

使用尾遞歸修改上面的列子：