許多教科書都把計(jì)算機(jī)階乘和菲波那契數(shù)列用來說明遞歸，非常不幸我們可愛的著名的老潭老師的《C語言程序設(shè)計(jì)》一書中就是從階乘的計(jì)算開始的函數(shù)遞歸。導(dǎo)致讀過這本經(jīng)書的同學(xué)們，看到階乘計(jì)算第一個(gè)想法就是遞歸。但是在階乘的計(jì)算里，遞歸并沒有提供任何優(yōu)越之處。在菲波那契數(shù)列中，它的效率更是低的非常恐怖。

這里有一個(gè)簡(jiǎn)單的程序，可用于說明遞歸。程序的目的是把一個(gè)整數(shù)從二進(jìn)制形式轉(zhuǎn)換為可打印的字符形式。例如：給出一個(gè)值4267，我們需要依次產(chǎn)生字符‘4'，‘2'，‘6'，和‘7'。就如在printf函數(shù)中使用了%d格式碼，它就會(huì)執(zhí)行類似處理。

我們采用的策略是把這個(gè)值反復(fù)除以10，并打印各個(gè)余數(shù)。例如，4267除10的余數(shù)是7，但是我們不能直接打印這個(gè)余數(shù)。我們需要打印的是機(jī)器字符集中表示數(shù)字‘7'的值。在ASCII碼中，字符‘7'的值是55，所以我們需要在余數(shù)上加上48來獲得正確的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性?！?'的ASCII碼是48，所以我們用余數(shù)加上‘0'，所以有下面的關(guān)系：

          ‘0'+ 0 =‘0'
          ‘0'+ 1 =‘1'
          ‘0'+ 2 =‘2'
      　　　    ...
從這些關(guān)系中，我們很容易看出在余數(shù)上加上‘0'就可以產(chǎn)生對(duì)應(yīng)字符的代碼。接著就打印出余數(shù)。下一步再取商的值，4267/10等于426。然后用這個(gè)值重復(fù)上述步驟。

這種處理方法存在的唯一問題是它產(chǎn)生的數(shù)字次序正好相反，它們是逆向打印的。所以在我們的程序中使用遞歸來修正這個(gè)問題。

我們這個(gè)程序中的函數(shù)是遞歸性質(zhì)的,因?yàn)樗艘粋€(gè)對(duì)自身的調(diào)用。乍一看，函數(shù)似乎永遠(yuǎn)不會(huì)終止。當(dāng)函數(shù)調(diào)用時(shí)，它將調(diào)用自身，第2次調(diào)用還將調(diào)用自身，以此類推，似乎永遠(yuǎn)調(diào)用下去。這也是我們?cè)趧偨佑|遞歸時(shí)最想不明白的事情。但是，事實(shí)上并不會(huì)出現(xiàn)這種情況。

這個(gè)程序的遞歸實(shí)現(xiàn)了某種類型的螺旋狀while循環(huán)。while循環(huán)在循環(huán)體每次執(zhí)行時(shí)必須取得某種進(jìn)展，逐步迫近循環(huán)終止條件。遞歸函數(shù)也是如此，它在每次遞歸調(diào)用后必須越來越接近某種限制條件。當(dāng)遞歸函數(shù)符合這個(gè)限制條件時(shí)，它便不在調(diào)用自身。

在程序中，遞歸函數(shù)的限制條件就是變量quotient為零。在每次遞歸調(diào)用之前，我們都把quotient除以10，所以每遞歸調(diào)用一次，它的值就越來越接近零。當(dāng)它最終變成零時(shí)，遞歸便告終止。

/*接受一個(gè)整型值（無符號(hào)0，把它轉(zhuǎn)換為字符并打印它，前導(dǎo)零被刪除*/

遞歸是如何幫助我們以正確的順序打印這些字符呢？下面是這個(gè)函數(shù)的工作流程。
1. 將參數(shù)值除以10
2. 如果quotient的值為非零，調(diào)用binary-to-ascii打印quotient當(dāng)前值的各位數(shù)字
3. 接著，打印步驟1中除法運(yùn)算的余數(shù)

注意在第2個(gè)步驟中，我們需要打印的是quotient當(dāng)前值的各位數(shù)字。我們所面臨的問題和最初的問題完全相同，只是變量quotient的值變小了。我們用剛剛編寫的函數(shù)（把整數(shù)轉(zhuǎn)換為各個(gè)數(shù)字字符并打印出來）來解決這個(gè)問題。由于quotient的值越來越小，所以遞歸最終會(huì)終止。

一旦你理解了遞歸，閱讀遞歸函數(shù)最容易的方法不是糾纏于它的執(zhí)行過程，而是相信遞歸函數(shù)會(huì)順利完成它的任務(wù)。如果你的每個(gè)步驟正確無誤，你的限制條件設(shè)置正確，并且每次調(diào)用之后更接近限制條件，遞歸函數(shù)總是能正確的完成任務(wù)。

但是，為了理解遞歸的工作原理，你需要追蹤遞歸調(diào)用的執(zhí)行過程，所以讓我們來進(jìn)行這項(xiàng)工作。追蹤一個(gè)遞歸函數(shù)的執(zhí)行過程的關(guān)鍵是理解函數(shù)中所聲明的變量是如何存儲(chǔ)的。當(dāng)函數(shù)被調(diào)用時(shí)，它的變量的空間是創(chuàng)建于運(yùn)行時(shí)堆棧上的。以前調(diào)用的函數(shù)的變量扔保留在堆棧上，但他們被新函數(shù)的變量所掩蓋，因此是不能被訪問的。

當(dāng)遞歸函數(shù)調(diào)用自身時(shí)，情況于是如此。每進(jìn)行一次新的調(diào)用，都將創(chuàng)建一批變量，他們將掩蓋遞歸函數(shù)前一次調(diào)用所創(chuàng)建的變量。當(dāng)我追蹤一個(gè)遞歸函數(shù)的執(zhí)行過程時(shí)，必須把分?jǐn)?shù)不同次調(diào)用的變量區(qū)分開來，以避免混淆。

程序中的函數(shù)有兩個(gè)變量：參數(shù)value和局部變量quotient。下面的一些圖顯示了堆棧的狀態(tài)，當(dāng)前可以訪問的變量位于棧頂。所有其他調(diào)用的變量飾以灰色的陰影，表示他們不能被當(dāng)前正在執(zhí)行的函數(shù)訪問。

假定我們以4267這個(gè)值調(diào)用遞歸函數(shù)。當(dāng)函數(shù)剛開始執(zhí)行時(shí)，堆棧的內(nèi)容如下圖所示：

不算遞歸調(diào)用語句本身，到目前為止所執(zhí)行的語句只是除法運(yùn)算以及對(duì)quotient的值進(jìn)行測(cè)試。由于遞歸調(diào)用這些語句重復(fù)執(zhí)行，所以它的效果類似循環(huán)：當(dāng)quotient的值非零時(shí)，把它的值作為初始值重新開始循環(huán)。但是，遞歸調(diào)用將會(huì)保存一些信息（這點(diǎn)與循環(huán)不同），也就好是保存在堆棧中的變量值。這些信息很快就會(huì)變得非常重要。

現(xiàn)在quotient的值變成了零，遞歸函數(shù)便不再調(diào)用自身，而是開始打印輸出。然后函數(shù)返回，并開始銷毀堆棧上的變量值。

每次調(diào)用putchar得到變量value的最后一個(gè)數(shù)字，方法是對(duì)value進(jìn)行模10取余運(yùn)算，其結(jié)果是一個(gè)0到9之間的整數(shù)。把它與字符常量‘0'相加，其結(jié)果便是對(duì)應(yīng)于這個(gè)數(shù)字的ASCII字符，然后把這個(gè)字符打印出來。

輸出4：

接著函數(shù)返回，它的變量從堆棧中銷毀。接著，遞歸函數(shù)的前一次調(diào)用重新繼續(xù)執(zhí)行，她所使用的是自己的變量，他們現(xiàn)在位于堆棧的頂部。因?yàn)樗膙alue值是42，所以調(diào)用putchar后打印出來的數(shù)字是2。

接著遞歸函數(shù)的這次調(diào)用也返回，它的變量也被銷毀，此時(shí)位于堆棧頂部的是遞歸函數(shù)再前一次調(diào)用的變量。遞歸調(diào)用從這個(gè)位置繼續(xù)執(zhí)行，這次打印的數(shù)字是6。在這次調(diào)用返回之前，堆棧的內(nèi)容如下：

現(xiàn)在我們已經(jīng)展開了整個(gè)遞歸過程，并回到該函數(shù)最初的調(diào)用。這次調(diào)用打印出數(shù)字7，也就是它的value參數(shù)除10的余數(shù)。

然后，這個(gè)遞歸函數(shù)就徹底返回到其他函數(shù)調(diào)用它的地點(diǎn)。
如果你把打印出來的字符一個(gè)接一個(gè)排在一起，出現(xiàn)在打印機(jī)或屏幕上，你將看到正確的值：4267
使用遞歸一定要有跳出的條件:
這是一個(gè)最簡(jiǎn)單的遞歸, 不過它會(huì)一直執(zhí)行, 可用 Ctrl+C 終止.





例輸出效果圖:

分析:
程序運(yùn)行到 A, 輸出了第一行.
此時(shí) n=1, 滿足 < 4 的條件, 繼續(xù)執(zhí)行 B 開始了自調(diào)用(接著會(huì)輸出第二行); 注意 n=1 時(shí)語句 C 還有待執(zhí)行.
...如此循環(huán), 一直到 n=4, A 可以執(zhí)行, 但因不滿足條件 B 執(zhí)行不了了; 終于在 n=4 時(shí)得以執(zhí)行 C.
但此時(shí)內(nèi)存中有四個(gè)函數(shù)都等待返回(分別是 n=1、2、3、4 時(shí)), 咱們分別叫它 f1、f2、f3、f4.
f4 執(zhí)行 C 輸出了第五行, 函數(shù)返回, 返回給 f3(此時(shí) n=3), f3 得以繼續(xù)執(zhí)行 C, 輸出了第六行.
f3 -> f2 -> 繼續(xù) C, 輸出了第七行.
f2 -> f1 -> 繼續(xù) C, 輸出了第八行, 執(zhí)行完畢!

如此看來, 遞歸函數(shù)還是很費(fèi)內(nèi)存的(有時(shí)不如直接使用循環(huán)), 但的確很巧妙.