- 相關(guān)推薦
對C語(yǔ)言中遞歸算法的深入解析
C通過(guò)運行時(shí)堆棧支持遞歸函數的實(shí)現。遞歸函數就是直接或間接調用自身的函數。下面是小編為大家帶來(lái)的對C語(yǔ)言中遞歸算法的深入解析，歡迎閱讀。
對C語(yǔ)言中遞歸算法的深入解析
許多教科書(shū)都把計算機階乘和菲波那契數列用來(lái)說(shuō)明遞歸，非常不幸我們可愛(ài)的著(zhù)名的老潭老師的《C語(yǔ)言程序設計》一書(shū)中就是從階乘的計算開(kāi)始的函數遞歸。導 致讀過(guò)這本經(jīng)書(shū)的同學(xué)們，看到階乘計算第一個(gè)想法就是遞歸。但是在階乘的計算里，遞歸并沒(méi)有提供任何優(yōu)越之處。在菲波那契數列中，它的效率更是低的非�？� 怖。
這里有一個(gè)簡(jiǎn)單的程序，可用于說(shuō)明遞歸。程序的目的是把一個(gè)整數從二進(jìn)制形式轉換為可打印的字符形式。例如：給出一個(gè)值4267，我們需要依次產(chǎn)生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函數中使用了%d格式碼，它就會(huì )執行類(lèi)似處理。
我們采用的策略是把這個(gè)值反復除以10，并打印各個(gè)余數。例如，4267除10的余數是7，但是我們不能直接打印這個(gè)余數。我們需要打印的是機器字符集中 表示數字‘7’的值。在A(yíng)SCII碼中，字符‘7’的值是55，所以我們需要在余數上加上48來(lái)獲得正確的字符，但是，使用字符常量而不是整型常量可以提 高程序的可移植性�！�0’的ASCII碼是48，所以我們用余數加上‘0’，所以有下面的關(guān)系：
‘0’+ 0 =‘0’
‘0’+ 1 =‘1’
‘0’+ 2 =‘2’
從這些關(guān)系中，我們很容易看出在余數上加上‘0’就可以產(chǎn)生對應字符的代碼。接著(zhù)就打印出余數。下一步再取商的值，4267/10等于426。然后用這個(gè)值重復上述步驟。
這種處理方法存在的唯一問(wèn)題是它產(chǎn)生的數字次序正好相反，它們是逆向打印的。所以在我們的程序中使用遞歸來(lái)修正這個(gè)問(wèn)題。
我們這個(gè)程序中的函數是遞歸性質(zhì)的,因為它包含了一個(gè)對自身的調用。乍一看，函數似乎永遠不會(huì )終止。當函數調用時(shí)，它將調用自身，第2次調用還將調用自身，以此類(lèi)推，似乎永遠調用下去。這也是我們在剛接觸遞歸時(shí)最想不明白的事情。但是，事實(shí)上并不會(huì )出現這種情況。
這個(gè)程序的遞歸實(shí)現了某種類(lèi)型的螺旋狀while循環(huán)。while循環(huán)在循環(huán)體每次執行時(shí)必須取得某種進(jìn)展，逐步迫近循環(huán)終止條件。遞歸函數也是如此，它在每次遞歸調用后必須越來(lái)越接近某種限制條件。當遞歸函數符合這個(gè)限制條件時(shí)，它便不在調用自身。
在程序中，遞歸函數的限制條件就是變量quotient為零。在每次遞歸調用之前，我們都把quotient除以10，所以每遞歸調用一次，它的值就越來(lái)越接近零。當它最終變成零時(shí)，遞歸便告終止。
/*接受一個(gè)整型值(無(wú)符號0，把它轉換為字符并打印它，前導零被刪除*/
#include
int binary_to_ascii( unsigned int value)
{
unsigned int quotient;
quotient = value / 10;
if( quotient != 0)
binary_to_ascii( quotient);
putchar ( value % 10 + '0' );
}
遞歸是如何幫助我們以正確的順序打印這些字符呢?下面是這個(gè)函數的工作流程。
1. 將參數值除以10
2. 如果quotient的值為非零，調用binary-to-ascii打印quotient當前值的各位數字
3. 接著(zhù)，打印步驟1中除法運算的余數
注意在第2個(gè)步驟中，我們需要打印的是quotient當前值的各位數字。我們所面臨的問(wèn)題和最初的問(wèn)題完全相同，只是變量quotient的 值變小了。我們用剛剛編寫(xiě)的函數(把整數轉換為各個(gè)數字字符并打印出來(lái))來(lái)解決這個(gè)問(wèn)題。由于quotient的值越來(lái)越小，所以遞歸最終會(huì )終止。
一旦你理解了遞歸，閱讀遞歸函數最容易的方法不是糾纏于它的執行過(guò)程，而是相信遞歸函數會(huì )順利完成它的任務(wù)。如果你的每個(gè)步驟正確無(wú)誤，你的限制條件設置正確，并且每次調用之后更接近限制條件，遞歸函數總是能正確的完成任務(wù)。
但是，為了理解遞歸的工作原理，你需要追蹤遞歸調用的執行過(guò)程，所以讓我們來(lái)進(jìn)行這項工作。追蹤一個(gè)遞歸函數的執行過(guò)程的關(guān)鍵是理解函數中所聲 明的變量是如何存儲的。當函數被調用時(shí)，它的變量的空間是創(chuàng )建于運行時(shí)堆棧上的。以前調用的函數的變量扔保留在堆棧上，但他們被新函數的變量所掩蓋，因此 是不能被訪(fǎng)問(wèn)的。
當遞歸函數調用自身時(shí)，情況于是如此。每進(jìn)行一次新的調用，都將創(chuàng )建一批變量，他們將掩蓋遞歸函數前一次調用所創(chuàng )建的變量。當我追蹤一個(gè)遞歸函數的執行過(guò)程時(shí)，必須把分數不同次調用的變量區分開(kāi)來(lái)，以避免混淆。
程序中的函數有兩個(gè)變量：參數value和局部變量quotient。下面的一些圖顯示了堆棧的狀態(tài)，當前可以訪(fǎng)問(wèn)的變量位于棧頂。所有其他調用的變量飾以灰色的陰影，表示他們不能被當前正在執行的函數訪(fǎng)問(wèn)。
假定我們以4267這個(gè)值調用遞歸函數。
執行除法之后，堆棧的內容如下：
接著(zhù)，if語(yǔ)句判斷出quotient的值非零，所以對該函數執行遞歸調用。當這個(gè)函數第二次被調用之初，堆棧的內容如下：
堆棧上創(chuàng )建了一批新的變量，隱藏了前面的那批變量，除非當前這次遞歸調用返回，否則他們是不能被訪(fǎng)問(wèn)的。再次執行除法運算之后，堆棧的內容如下：
quotient的值現在為42，仍然非零，所以需要繼續執行遞歸調用，并再創(chuàng )建一批變量。在執行完這次調用的出發(fā)運算之后，堆棧的內容如下：
此時(shí)，quotient的值還是非零，仍然需要執行遞歸調用。在執行除法運算之后，堆棧的內容如下：
不算遞歸調用語(yǔ)句本身，到目前為止所執行的語(yǔ)句只是除法運算以及對quotient的值進(jìn)行測試。由于遞歸調用這些語(yǔ)句重復執行，所以它的效果 類(lèi)似循環(huán)：當quotient的值非零時(shí)，把它的值作為初始值重新開(kāi)始循環(huán)。但是，遞歸調用將會(huì )保存一些信息(這點(diǎn)與循環(huán)不同)，也就好是保存在堆棧中的 變量值。這些信息很快就會(huì )變得非常重要。
現在quotient的值變成了零，遞歸函數便不再調用自身，而是開(kāi)始打印輸出。然后函數返回，并開(kāi)始銷(xiāo)毀堆棧上的'變量值。
每次調用putchar得到變量value的最后一個(gè)數字，方法是對value進(jìn)行模10取余運算，其結果是一個(gè)0到9之間的整數。把它與字符常量‘0’相加，其結果便是對應于這個(gè)數字的ASCII字符，然后把這個(gè)字符打印出來(lái)。
輸出4：
接著(zhù)函數返回，它的變量從堆棧中銷(xiāo)毀。接著(zhù)，遞歸函數的前一次調用重新繼續執行，她所使用的是自己的變量，他們現在位于堆棧的頂部。因為它的value值是42，所以調用putchar后打印出來(lái)的數字是2。
輸出42：
接著(zhù)遞歸函數的這次調用也返回，它的變量也被銷(xiāo)毀，此時(shí)位于堆棧頂部的是遞歸函數再前一次調用的變量。遞歸調用從這個(gè)位置繼續執行，這次打印的數字是6。在這次調用返回之前，堆棧的內容如下：
輸出426：
現在我們已經(jīng)展開(kāi)了整個(gè)遞歸過(guò)程，并回到該函數最初的調用。這次調用打印出數字7，也就是它的value參數除10的余數。
輸出4267：
然后，這個(gè)遞歸函數就徹底返回到其他函數調用它的地點(diǎn)。
如果你把打印出來(lái)的字符一個(gè)接一個(gè)排在一起，出現在打印機或屏幕上，你將看到正確的值：4267
漢諾塔問(wèn)題遞歸算法分析：
一個(gè)廟里有三個(gè)柱子，第一個(gè)有64個(gè)盤(pán)子，從上往下盤(pán)子越來(lái)越大。要求廟里的老和尚把這64個(gè)盤(pán)子全部移動(dòng)到第三個(gè)柱子上。移動(dòng)的時(shí)候始終只能小盤(pán)子壓著(zhù)大盤(pán)子。而且每次只能移動(dòng)一個(gè)。
1、此時(shí)老和尚(后面我們叫他第一個(gè)和尚)覺(jué)得很難，所以他想：要是有一個(gè)人能把前63個(gè)盤(pán)子先移動(dòng)到第二個(gè)柱子上，我再把最后一個(gè)盤(pán)子直接移 動(dòng)到第三個(gè)柱子，再讓那個(gè)人把剛才的前63個(gè)盤(pán)子從第二個(gè)柱子上移動(dòng)到第三個(gè)柱子上，我的任務(wù)就完成了，簡(jiǎn)單。所以他找了比他年輕的和尚(后面我們叫他第 二個(gè)和尚)，命令：
�、� 你丫把前63個(gè)盤(pán)子移動(dòng)到第二柱子上
�、� 然后我自己把第64個(gè)盤(pán)子移動(dòng)到第三個(gè)柱子上后
�、� 你把前63個(gè)盤(pán)子移動(dòng)到第三柱子上
2、第二個(gè)和尚接了任務(wù)，也覺(jué)得很難，所以他也和第一個(gè)和尚一樣想：要是有一個(gè)人能把前62個(gè)盤(pán)子先移動(dòng)到第三個(gè)柱子上，我再把最后一個(gè)盤(pán)子直接移動(dòng)到第 二個(gè)柱子，再讓那個(gè)人把剛才的前62個(gè)盤(pán)子從第三個(gè)柱子上移動(dòng)到第三個(gè)柱子上，我的任務(wù)就完成了，簡(jiǎn)單。所以他也找了比他年輕的和尚(后面我們叫他第三和 尚)，命令：
�、� 你把前62個(gè)盤(pán)子移動(dòng)到第三柱子上
�、� 然后我自己把第63個(gè)盤(pán)子移動(dòng)到第二個(gè)柱子上后
�、� 你把前62個(gè)盤(pán)子移動(dòng)到第二柱子上
3、第三個(gè)和尚接了任務(wù)，又把移動(dòng)前61個(gè)盤(pán)子的任務(wù)依葫蘆話(huà)瓢的交給了第四個(gè)和尚，等等遞推下去，直到把任務(wù)交給了第64個(gè)和尚為止(估計第64個(gè)和尚很郁悶，沒(méi)機會(huì )也命令下別人，因為到他這里盤(pán)子已經(jīng)只有一個(gè)了)。
4、到此任務(wù)下交完成，到各司其職完成的時(shí)候了。完成回推了：
第64個(gè)和尚移動(dòng)第1個(gè)盤(pán)子，把它移開(kāi)，然后第63個(gè)和尚移動(dòng)他給自己分配的第2個(gè)盤(pán)子。
第64個(gè)和尚再把第1個(gè)盤(pán)子移動(dòng)到第2個(gè)盤(pán)子上。到這里第64個(gè)和尚的任務(wù)完成，第63個(gè)和尚完成了第62個(gè)和尚交給他的任務(wù)的第一步。
從上面可以看出，只有第64個(gè)和尚的任務(wù)完成了，第63個(gè)和尚的任務(wù)才能完成，只有第2個(gè)和尚----第64個(gè)和尚的任務(wù)完成后，第1個(gè)和尚的任務(wù)才能完成。這是一個(gè)典型的遞歸問(wèn)題。 現在我們以有3個(gè)盤(pán)子來(lái)分析：
第1個(gè)和尚命令：
�、� 第2個(gè)和尚你先把第一柱子前2個(gè)盤(pán)子移動(dòng)到第二柱子。(借助第三個(gè)柱子)
�、� 第1個(gè)和尚我自己把第一柱子最后的盤(pán)子移動(dòng)到第三柱子。
�、� 第2個(gè)和尚你把前2個(gè)盤(pán)子從第二柱子移動(dòng)到第三柱子。
很顯然，第二步很容易實(shí)現(哎，人總是自私地，把簡(jiǎn)單留給自己，困難的給別人)。
其中第一步，第2個(gè)和尚他有2個(gè)盤(pán)子，他就命令：
�、� 第3個(gè)和尚你把第一柱子第1個(gè)盤(pán)子移動(dòng)到第三柱子。(借助第二柱子)
�、� 第2個(gè)和尚我自己把第一柱子第2個(gè)盤(pán)子移動(dòng)到第二柱子上。
�、� 第3個(gè)和尚你把第1個(gè)盤(pán)子從第三柱子移動(dòng)到第二柱子。
同樣，第二步很容易實(shí)現，但第3個(gè)和尚他只需要移動(dòng)1個(gè)盤(pán)子，所以他也不用在下派任務(wù)了。(注意：這就是停止遞歸的條件，也叫邊界值)
第三步可以分解為，第2個(gè)和尚還是有2個(gè)盤(pán)子，命令：
�、� 第3個(gè)和尚你把第二柱子上的第1個(gè)盤(pán)子移動(dòng)到第一柱子。
�、� 第2個(gè)和尚我把第2個(gè)盤(pán)子從第二柱子移動(dòng)到第三柱子。
�、� 第3個(gè)和尚你把第一柱子上的盤(pán)子移動(dòng)到第三柱子。
分析組合起來(lái)就是：1→3 1→2 3→2 借助第三個(gè)柱子移動(dòng)到第二個(gè)柱子 |1→3 自私人留給自己的活| 2→1 2→3 1→3借助第一個(gè)柱子移動(dòng)到第三個(gè)柱子|共需要七步。
如果是4個(gè)盤(pán)子，則第一個(gè)和尚的命令中第1步和第3步各有3個(gè)盤(pán)子，所以各需要7步，共14步，再加上第1個(gè)和尚的1步，所以4個(gè)盤(pán)子總共需要移動(dòng) 7+1+7=15步，同樣，5個(gè)盤(pán)子需要15+1+15=31步，6個(gè)盤(pán)子需要31+1+31=64步……由此可以知道，移動(dòng)n個(gè)盤(pán)子需要(2的n次 方)-1步。
從上面整體綜合分析可知把n個(gè)盤(pán)子從1座(相當第一柱子)移到3座(相當第三柱子)：
(1)把1座上(n-1)個(gè)盤(pán)子借助3座移到2座。
(2)把1座上第n個(gè)盤(pán)子移動(dòng)3座。
(3)把2座上(n-1)個(gè)盤(pán)子借助1座移動(dòng)3座。
下面用hanoi(n,a,b,c)表示把1座n個(gè)盤(pán)子借助2座移動(dòng)到3座。
很明顯: (1)步上是 hanoi(n-1,1,3,2)
(3)步上是 hanoi(n-1,2,1,3)
用C語(yǔ)言表示出來(lái)，就是：
#include
int method(int n,char a, char b)
{
printf("number..%d..form..%c..to..%c.."n",n,a,b);
return 0;
}
int hanoi(int n,char a,char b,char c)
{
if( n==1 ) move (1,a,c);
else
{
hanoi(n-1,a,c,b);
move(n,a,c);
hanoi(n-1,b,a,c);
};
return 0;
}
int main()
{
int num;
scanf("%d",&num);
hanoi(num,'A','B','C');
return 0;
}
【對C語(yǔ)言中遞歸算法的深入解析】相關(guān)文章：
深入解釋c語(yǔ)言中的遞歸算法07-17
C語(yǔ)言中遞歸算法的剖析08-15
C語(yǔ)言中野指針的深入解析08-06
深入解析C語(yǔ)言中的數值與真假08-14
C語(yǔ)言中實(shí)現KMP算法實(shí)例08-09
C語(yǔ)言中壓縮字符串的算法07-27