遞歸這個詞，生活中應該比較少用到稠歉，你可能對它比較陌生掰担，而本文的主題就是它。舉個從小就聽過的例子：從前有座山怒炸，山里有座廟带饱，廟里有個和尚，和尚在講故事阅羹，從前有座山勺疼，山里有座廟...
再舉個例子，下圖就可以看做近似的遞歸捏鱼，
再來看一下百度對遞歸詞匯的解釋执庐，
相信通過上面的解釋，大家對遞歸有一定的認識了穷躁。接下來耕肩，我們正式來講講程序設計中的遞歸函數。
遞歸函數就是函數直接或者間接調用自身的函數问潭。許多教科書把階乘運算用來說明遞歸猿诸，這是非常不幸的。因為這個時候使用狡忙，它的效率非常之低梳虽。
這里有一個簡單的程序，可用于說明遞歸灾茁。程序的目的是把一個整數轉換為可打印的字符形式窜觉。例如，給出一個值4267北专，我們需要依次產生字符'4'禀挫、'2'、'6'拓颓、'7'语婴。
我們采用的策略是把這個值反復對10取余得到余數處理打印后，并除以10驶睦。例如砰左，4267除10的余數是7，但是我們不能直接打印這個余數场航。我們需要打印的是機器字符集中表示數字'7'的值缠导。在ASCII碼中，字符'7'的值是55溉痢，所以我們需要在余數上加上48來獲得正確的字符僻造。但是憋他，使用字符常量而不是整型常量可以提高程序的可移植性〉找猓考慮下面的關系：
'0' + 0 = '0'
'0' + 1 = '1'
'0' + 2 = '2'
從這些關系中举瑰，我們很容易看出在余數上機上'0'就可以產生對應字符的代碼。接著就打印出余數蔬螟。下一步是取得商，4267/10等于426（整型取整）汽畴。然后用這個得到的值重復上述步驟旧巾。
這種處理方法存在的問題是它產生的數字次序正好相反，它們是逆向打印的忍些。在下面的程序中鲁猩，我們就用遞歸來修正這個問題。
void binary_to_ascii(unsigned int value)
{
? unsigned int quotient = value / 10;
? if (quotient !=0)
? ? binary_to_ascii(quotient);
? ? putchar(value % 10 + '0');
}
上面程序中的函數是遞歸性質的罢坝，因為它包含了一個對自身的調用廓握。乍一看，函數似乎永遠也不會終止嘁酿，當函數調用時隙券，它將調用自身，第二次調用還是調用自身闹司，以此類推娱仔，似乎永遠調用下去。但是游桩，事實上并不會出現這種情況牲迫。
這個程序的遞歸實現了某種類型的螺旋狀while循環(huán)。while循環(huán)在循環(huán)體每次執(zhí)行時必須取得某種進展借卧，逐步迫近循環(huán)終止條件盹憎。遞歸函數也是如此，它在每次遞歸調用后必須越來越接近某種限制條件铐刘。當遞歸函數符合這個限制條件時陪每，它便不再調用自身。
該程序中滨达，遞歸函數的限制條件就是變量quotient為0奶稠。在每次遞歸調用之前，我們都把quotient除以10捡遍，所以每遞歸一次锌订，它的值就更接近0。當它最終變成0時画株，遞歸便告終了辆飘。
那么我們再來分析下啦辐，遞歸是如何幫我們以正確的順序打印這些字符的呢？下面是這個函數的工作流程蜈项。
1.將參數值除以10
2.如果quotient的值為非零芹关，調用binary_to_ascii打印quotient當前值的各位數字
3.接著，打印步驟1中取余運算的余數
注意在第二個步驟中紧卒，我們要打印的是quotient當前值的各位數字侥衬。我們所面臨的問題和最初的問題完全相同，只是變量quotient的值變小了跑芳。我們用剛剛編寫的函數（把整數轉換為各個數字字符并打印出來）來解決這個問題轴总。由于quotient的值越來越小，所以遞歸最終會終止博个。
一旦你理解了遞歸怀樟，閱讀遞歸函數最容易的方法不是糾纏于它的執(zhí)行過程，而是相信遞歸函數會順利完成它的任務盆佣。如果你的每個步驟正確無誤往堡，你的限制條件設置正確，并且每次調用之后更接近限制條件共耍，遞歸函數總是能夠正確地完成任務虑灰。
追蹤遞歸函數
為了理解遞歸的工作原理，你需要追蹤遞歸調用的執(zhí)行過程征堪，所以讓我們來進行這項工作瘩缆。追蹤一個遞歸函數執(zhí)行過程的關鍵是理解函數中所聲明的變量是如何存儲的。當函數被調用時佃蚜，它的變量的空間是創(chuàng)建于運行的堆棧上的庸娱。以前調用的函數的變量仍保留在堆棧上，但它們被新函數的變量所掩蓋谐算，因此是不能訪問的熟尉。
當遞歸函數調用自身時，情況也是如此洲脂。每進行一次新的調用斤儿，都將創(chuàng)建一批變量，它們掩蓋遞歸函數前一次調用所創(chuàng)建的變量恐锦。當我們追蹤一個遞歸函數的執(zhí)行過程時往果，必須把分屬不同次調用的變量區(qū)分開來，避免混淆一铅。
我們上面寫的函數中有兩個變量：參數value和局部變量quotient陕贮。下面的一些圖顯示了堆棧的狀態(tài)，當前可以訪問的變量位于棧頂潘飘。所有其他調用的變量飾以灰色陰影肮之，表示它們不能被當前正在執(zhí)行的函數訪問掉缺。
假定我們以4267這個值調用遞歸函數。當函數開始執(zhí)行時戈擒，堆棧的內容如下圖所示眶明。
執(zhí)行除法運算后，堆棧的內容如下：
接著筐高，if語句判斷出quotient的值非零搜囱，所以對該函數進行遞歸調用。當這個函數第二次被調用之初凯傲，堆棧的內容如下：
堆棧上創(chuàng)建了一批新的變量犬辰，隱藏了前面的那些變量，除非當前這次遞歸調用返回冰单，否則它們是不能被訪問的。再次執(zhí)行除法運算之后堆棧的內容如下：
quotient的值現在為42灸促，仍然非零诫欠，所以需要繼續(xù)執(zhí)行遞歸調用，并再創(chuàng)建一批變量浴栽。在執(zhí)行完這次調用的除法運算之后荒叼，堆棧的內容如下：
此時，quotient的值還是非零典鸡，仍然需要執(zhí)行遞歸調用被廓。在執(zhí)行除法運算之后，堆棧的內容如下：
不算遞歸調用語句本身萝玷，到目前為止所執(zhí)行的語句只是除法運算以及對quotient的值進行測試嫁乘。由于遞歸調用使這些語句重復執(zhí)行，所以它的效果類似循環(huán)：當quotient的值非零實時球碉，把它的值作為初始值重新開始循環(huán)蜓斧。但是，遞歸調用將會保存一些信息（這點與循環(huán)不同）睁冬，也就是保存在堆棧中的變量值挎春。這些信息很快就會變得非常重要。
現在quotient的值變成了0豆拨，遞歸函數便不再調用自身直奋，而是開始打印輸出。然后函數返回施禾，并開始銷毀堆棧上的變量值脚线。
每次調用putchar得到變量value的最后一個數字，方法是對value進行模10取余運算拾积，其結果是一個0到9之間的整數殉挽。當它與字符常量'0'相加丰涉，其結果便是對應于這個數字的ASCII字符，然后把這個字符打印出來斯碌。
接著函數返回一死，它的變量從堆棧中銷毀。接著傻唾，遞歸函數的前一次調用重新繼續(xù)執(zhí)行投慈，它所使用的是自己的變量，它們現在位于堆棧的頂部冠骄。因為它的value值是42伪煤，所以調用putchar后打印出來的數字是2。
接著遞歸函數的這次調用也返回凛辣，它的變量也被銷毀抱既，此時位于堆棧頂部的是遞歸函數再前一次調用的變量。遞歸調用從這個位置繼續(xù)執(zhí)行扁誓，這次打印的數字是6防泵。在這次調用返回之前，堆棧的內容如下：
現在我們已經展開了整個遞歸過程蝗敢，并回到該函數最初的調用捷泞。這次調用打印出的數字7，也就是它的value參數除10的余數寿谴。
然后锁右，整個遞歸函數就徹底返回到一開始調用它的地點。
如果你把打印出來的字符一個接一個排在一起讶泰，出現在打印機或屏幕上咏瑟，你將看到正確的值：4267。
遞歸與迭代
遞歸是一種強有力的技巧峻厚，但也和其他技巧一樣响蕴，它可能被誤用。這里就有一個例子惠桃，如下圖所示：
這個定義同時具備了我們開始討論遞歸所需要的兩個特性：存在限制條件浦夷，當符合這個條件時遞歸便不再繼續(xù)：每次遞歸調用之后越來越接近這個限制條件。
用這種方式定義階乘往往會引導人們使用遞歸來實現階乘函數辜王，如下程序：
? ? long fun(int n)
? ? {
? ? ? if (n <= 0)
? ? ? ? return 1;
? ? ? else
? ? ? ? return n * fun(n-1);
? ? }
這個函數能夠產生正確的結果劈狐，但它并不是遞歸的良好用法。遞歸調用將涉及一些運行時開銷------參數必須壓倒堆棧中呐馆，為局部變量分配內存空間（所有遞歸均是如此肥缔，并非特指這個例子），寄存器的值必須保存等汹来。當遞歸函數的每次調用返回時续膳，上述這些操作必須還原改艇，恢復成原來的樣子。所以坟岔，基于這些開銷谒兄，對于這個程序而言，它并沒有簡化問題的解決方案社付。
下面使用循環(huán)計算相同的結果：
? ? long fun(int n)
? ? {
? ? ? int result = -1;
? ? ? while(n > 1)
? ? ? {
? ? ? ? result *= n;
? ? ? ? n -= 1;
? ? ? }
? ? ? return result;
? ? }
盡管這個使用簡單循環(huán)的程序不甚符合前面階乘的數學定義承疲，但它卻能更為有效地計算出相同的結果。如果你仔細觀察遞歸函數鸥咖，你會發(fā)現遞歸調用是函數所執(zhí)行的最后一項任務燕鸽。這個函數是尾部遞歸（tail recursion）的一個例子。由于函數在遞歸調用返回之后不再執(zhí)行任何任務啼辣，所以尾部遞歸可以很方便地轉換成一個簡單循環(huán)啊研，完成相同的任務。
