遞歸這個詞，生活中應該比較少用到，你可能對它比較陌生，而本文的主題就是它。舉個從小就聽過的例子：從前有座山，山里有座廟，廟里有個和尚，和尚在講故事，從前有座山，山里有座廟...

再舉個例子，下圖就可以看做近似的遞歸，


再來看一下百度對遞歸詞匯的解釋，


相信通過上面的解釋，大家對遞歸有一定的認識了。接下來，我們正式來講講程序設計中的遞歸函數(shù)。

遞歸函數(shù)就是函數(shù)直接或者間接調(diào)用自身的函數(shù)。許多教科書把階乘運算用來說明遞歸，這是非常不幸的。因為這個時候使用，它的效率非常之低。

這里有一個簡單的程序，可用于說明遞歸。程序的目的是把一個整數(shù)轉換為可打印的字符形式。例如，給出一個值4267，我們需要依次產(chǎn)生字符'4'、'2'、'6'、'7'。

我們采用的策略是把這個值反復對10取余得到余數(shù)處理打印后，并除以10。例如，4267除10的余數(shù)是7，但是我們不能直接打印這個余數(shù)。我們需要打印的是機器字符集中表示數(shù)字'7'的值。在ASCII碼中，字符'7'的值是55，所以我們需要在余數(shù)上加上48來獲得正確的字符。但是，使用字符常量而不是整型常量可以提高程序的可移植性?？紤]下面的關系：

'0' + 0 = '0'

'0' + 1 = '1'

'0' + 2 = '2'

從這些關系中，我們很容易看出在余數(shù)上機上'0'就可以產(chǎn)生對應字符的代碼。接著就打印出余數(shù)。下一步是取得商，4267/10等于426（整型取整）。然后用這個得到的值重復上述步驟。

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

void binary_to_ascii(unsigned int value)

{

? unsigned int quotient = value / 10;

? if (quotient !=0)

? ? binary_to_ascii(quotient);

? ? putchar(value % 10 + '0');

}

上面程序中的函數(shù)是遞歸性質(zhì)的，因為它包含了一個對自身的調(diào)用。乍一看，函數(shù)似乎永遠也不會終止，當函數(shù)調(diào)用時，它將調(diào)用自身，第二次調(diào)用還是調(diào)用自身，以此類推，似乎永遠調(diào)用下去。但是，事實上并不會出現(xiàn)這種情況。

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

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

那么我們再來分析下，遞歸是如何幫我們以正確的順序打印這些字符的呢？下面是這個函數(shù)的工作流程。

1.將參數(shù)值除以10

2.如果quotient的值為非零，調(diào)用binary_to_ascii打印quotient當前值的各位數(shù)字

3.接著，打印步驟1中取余運算的余數(shù)

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

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

追蹤遞歸函數(shù)

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

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

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

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


執(zhí)行除法運算后，堆棧的內(nèi)容如下：


接著，if語句判斷出quotient的值非零，所以對該函數(shù)進行遞歸調(diào)用。當這個函數(shù)第二次被調(diào)用之初，堆棧的內(nèi)容如下：


堆棧上創(chuàng)建了一批新的變量，隱藏了前面的那些變量，除非當前這次遞歸調(diào)用返回，否則它們是不能被訪問的。再次執(zhí)行除法運算之后堆棧的內(nèi)容如下：


quotient的值現(xiàn)在為42，仍然非零，所以需要繼續(xù)執(zhí)行遞歸調(diào)用，并再創(chuàng)建一批變量。在執(zhí)行完這次調(diào)用的除法運算之后，堆棧的內(nèi)容如下：


此時，quotient的值還是非零，仍然需要執(zhí)行遞歸調(diào)用。在執(zhí)行除法運算之后，堆棧的內(nèi)容如下：


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

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

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


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


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


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


然后，整個遞歸函數(shù)就徹底返回到一開始調(diào)用它的地點。

如果你把打印出來的字符一個接一個排在一起，出現(xiàn)在打印機或屏幕上，你將看到正確的值：4267。

遞歸與迭代

遞歸是一種強有力的技巧，但也和其他技巧一樣，它可能被誤用。這里就有一個例子，如下圖所示：


這個定義同時具備了我們開始討論遞歸所需要的兩個特性：存在限制條件，當符合這個條件時遞歸便不再繼續(xù)：每次遞歸調(diào)用之后越來越接近這個限制條件。

用這種方式定義階乘往往會引導人們使用遞歸來實現(xiàn)階乘函數(shù)，如下程序：

? ? long fun(int n)

? ? {

? ? ? if (n <= 0)

? ? ? ? return 1;

? ? ? else

? ? ? ? return n * fun(n-1);

? ? }

這個函數(shù)能夠產(chǎn)生正確的結果，但它并不是遞歸的良好用法。遞歸調(diào)用將涉及一些運行時開銷------參數(shù)必須壓倒堆棧中，為局部變量分配內(nèi)存空間（所有遞歸均是如此，并非特指這個例子），寄存器的值必須保存等。當遞歸函數(shù)的每次調(diào)用返回時，上述這些操作必須還原，恢復成原來的樣子。所以，基于這些開銷，對于這個程序而言，它并沒有簡化問題的解決方案。

下面使用循環(huán)計算相同的結果：

? ? long fun(int n)

? ? {

? ? ? int result = -1;

? ? ? while(n > 1)

? ? ? {

? ? ? ? result *= n;

? ? ? ? n -= 1;

? ? ? }

? ? ? return result;

? ? }

盡管這個使用簡單循環(huán)的程序不甚符合前面階乘的數(shù)學定義，但它卻能更為有效地計算出相同的結果。如果你仔細觀察遞歸函數(shù)，你會發(fā)現(xiàn)遞歸調(diào)用是函數(shù)所執(zhí)行的最后一項任務。這個函數(shù)是尾部遞歸（tail recursion）的一個例子。由于函數(shù)在遞歸調(diào)用返回之后不再執(zhí)行任何任務，所以尾部遞歸可以很方便地轉換成一個簡單循環(huán)，完成相同的任務。