C語(yǔ)言遞歸復(fù)習(xí)過程

1、精品文檔精品文檔C語(yǔ)言遞歸1 簡(jiǎn)介遞歸，作為C語(yǔ)言最經(jīng)典的算法之一，是一種非常有用的程序設(shè)計(jì)方法。 雖然用遞歸算法編寫的程序結(jié)構(gòu)清晰， 具有很好的可讀性，還往往使某些看起來 不易解決的問題變得容易解決。但在遞歸函數(shù)中，由于存在著自調(diào)用過程，程序控制反復(fù)進(jìn)入其自身，使程序的分析設(shè)計(jì)有一定困難，致使很多初學(xué)者往往對(duì)遞 歸迷惑不解， 也在這上面花了不少的時(shí)間， 卻收效甚微。 那么， 究竟什么是遞歸？怎么實(shí)現(xiàn)遞歸呢？所謂遞歸，簡(jiǎn)而言之就是 在調(diào)用一個(gè)函數(shù)的過程中又直接或間接地調(diào)用該函 數(shù)本身，以實(shí)現(xiàn)層次數(shù)據(jù)結(jié)構(gòu)的查詢和訪問_。在函數(shù)中直接調(diào)用函數(shù)本身，稱為 直接遞歸調(diào)用。在函數(shù)中調(diào)用其它函數(shù)， 其它函

2、數(shù)又調(diào)用原函數(shù)，這就構(gòu)成了函數(shù)自身的間接調(diào)用，稱為 間接遞歸調(diào)用。2 條件而采用遞歸方法來解決問題，必須符合以下三個(gè)條件：1、可以把要解決的問題轉(zhuǎn)化為一個(gè)新問題，而這個(gè)新的問題的解決方法仍與原來的解決方法相同，只是所處理的對(duì)象有規(guī)律地遞增或遞減。 說明：解決問題的方法相同，調(diào)用函數(shù)的參數(shù)每次不同(有規(guī)律的遞 增或遞減)，如果沒有規(guī)律也就不能適用遞歸調(diào)用。2、可以應(yīng)用這個(gè)轉(zhuǎn)化過程使問題得到解決。說明：使用其他的辦法比較麻煩或很難解決，而使用遞歸的方法可以很好地解決問題3、必定要有一個(gè)明確的結(jié)束遞歸的條件。說明：一定要能夠在適當(dāng)?shù)牡?方結(jié)束遞歸調(diào)用。不然可能導(dǎo)致系統(tǒng)崩潰。3 求 n!問題好知道是這

3、樣以后；我們來寫一個(gè)眾多教材上的程序：使用遞歸的方法求n!當(dāng)n1時(shí)，求n!的問題可以轉(zhuǎn)化為n*(n-1)!的新問題。比如n=4: 第一部分：4*3*2*1n*( n-1)!第二部分：3*2*1(n-1)( n-2)!第三部分：2*1 (n-2)( n-3)!第四部分：1 (n-4)!4-4=0，得到值1,結(jié)束遞歸。源程序如下：#in elude 精品文檔精品文檔int fac( int n)int c;printf( now the number is %d , n);printf( now the number is %d and the %d! is %d, n, n,c);getchar

4、();return c;void main()int n=4;printf( result is %d.n,fac( n);圖 1;如的運(yùn)行輅果 A可以看到，加上兩條printf()和getchar()語(yǔ)句后，可以察看各級(jí)調(diào)用及其中間 答案，很清楚的看到程序的執(zhí)行過程。運(yùn)行結(jié)果如圖1所示， 當(dāng)主函數(shù)第一次調(diào)用fac()函數(shù)的時(shí)候， 由于n=4不 等于0和1，并不立即返回結(jié)果1，而是執(zhí)行c=n*fac(n-1)，用實(shí)參n-1(值為3) 調(diào)用fac()函數(shù)自己，即遞歸調(diào)用fac(3)。于是進(jìn)入第二層調(diào)用fac()，這時(shí)也沒有 得出結(jié)果，繼續(xù)用實(shí)參n-1(值為aIDfJTt he thwthethe

5、thethethetheniinineinMRb&rnumbernumberrmnheinunb&rnuinhernunbeiandandandandthethethethe4 4 126126 2 2 s s s ss s s s i i iiiii i.曹12341234getchar();精品文檔2)調(diào)用fac()函數(shù)自己。同樣經(jīng)過第三層調(diào)用精品文檔后進(jìn)入第四層調(diào)用，這時(shí)候n=1,算出1!=1，滿足結(jié)束遞歸的條件，然后把得出 的結(jié)果1返回給第三次調(diào)用的fac函數(shù)，得出2*1!=2，然后把結(jié)果2返回給第二 次調(diào)用的fac函數(shù)，得出3*2!=6，最后第一次調(diào)用的fac函數(shù)根據(jù)

6、第二次調(diào)用的 返回值算出4!=4*3!=4*6=24，結(jié)束整個(gè)遞歸調(diào)用，得出最終結(jié)果并輸出。我們做事情，一般都是從頭開始的，而遞歸卻是從末尾開始的。比如上面的函數(shù)， 當(dāng)n1的時(shí)候， 就只能求助于n-1,而(n-1)1時(shí)， 就求助于n-2,然后 直到(n-k)=1時(shí)，函數(shù)fac終于有了返回值1了，它再?gòu)念^開始計(jì)算，然后一直算 到n為止。所以說，遞歸簡(jiǎn)直就是一個(gè)數(shù)學(xué)模型，它的工作過程就是自己調(diào)用自己。4 說明以下是幾點(diǎn)對(duì)遞歸的說明：(1) .當(dāng)函數(shù)自己調(diào)用自己時(shí)，系統(tǒng)將自動(dòng)把函數(shù)中當(dāng)前的變量和形參暫時(shí)保留起來，在新一輪的調(diào)用過程中，系統(tǒng)為新調(diào)用的函數(shù)所用到的變量和 形參開辟另外的存儲(chǔ)單元(內(nèi)存空間

7、)。每次調(diào)用函數(shù)所使用的變量在 不同的內(nèi)存空間。(2) .遞歸調(diào)用的層次越多，同名變量的占用的存儲(chǔ)單元也就越多。一定要記住，每次函數(shù)的調(diào)用，系統(tǒng)都會(huì)為該函數(shù)的變量開辟新的內(nèi)存空間。(3) .當(dāng)本次調(diào)用的函數(shù)運(yùn)行結(jié)束時(shí)，系統(tǒng)將釋放本次調(diào)用時(shí)所占用的內(nèi)存空間。程序的流程返回到上一層的調(diào)用點(diǎn)，同時(shí)取得當(dāng)初進(jìn)入該層時(shí)，函 數(shù)中的變量和形參所占用的內(nèi)存空間的數(shù)據(jù)。(4) .在開發(fā)過程中使用printf()和getchar()可以看到執(zhí)行過程，并且可以在發(fā)現(xiàn)錯(cuò)誤后停止運(yùn)行。很多人說所有遞歸問題都可以用非遞歸的方法來解決， 能不用遞歸就不用遞 歸。但是對(duì)于一些比較復(fù)雜的遞歸問題用非遞歸的方法往往使程序變得十

8、分復(fù)雜 難以讀懂，而函數(shù)的遞歸調(diào)用在解決這類問題時(shí)能使程序簡(jiǎn)潔明了有較好的可讀 性，因此很多問題用遞歸可很容易解決。同時(shí)由于遞歸調(diào)用過程中，系統(tǒng)要為每一層調(diào)用中的變量開辟內(nèi)存空間、 要記住每一層調(diào)用后的返回點(diǎn)、 要增加許多額 外的開銷，因此函數(shù)的遞歸調(diào)用通常會(huì)降低程序的運(yùn)行效率(在許多情況下，速 度的差別不太明顯)。5 動(dòng)物繁殖問題我曾經(jīng)碰到過這樣一個(gè)動(dòng)物繁殖問題：若一頭小母牛，從出生起第四個(gè)年頭 開始每年生一頭母牛，按此規(guī)律，第n年時(shí)有多少頭母牛？如果不用遞歸函數(shù)來做，每當(dāng)母牛到第4歲的時(shí)候才會(huì)生下一頭小母牛，所精品文檔精品文檔以，每年增加的新的1歲小母牛都是上一年3歲的母牛加上4歲的母牛生

9、下數(shù)量 之和，分析過程如圖2所示3F力擲向母辛2歹的対q3寧的毋咋鑼鑼臥臥上旳鐲咔L1C00201003aQ04iCi5116!1i7212832I39,3Z4104XLL售e4121_ /fl& _E 3=母牛鑒殖間題分析過程給出程序如下:# in elude void main()int i,n;int f1=1,f2=0,f3=0,f4=0;pri ntf( please in put how many years it past: n);seanf( %d,&n);for (i=2;i=n;i+)f4=f4+f3;printf( now you have %d catt

10、le!n ,f1+f2+f3+f4);while (1)；程序雖然簡(jiǎn)短，但是可讀性太差，不易理解。那么如果用遞歸函數(shù)求此問題 呢？我們先寫出函數(shù)表達(dá)式：f(n )=f( n-1)+f( n-3)為什么f(n)=f(n-1)+f(n-3)呢，請(qǐng)看：精品文檔精品文檔f(n )-f( n-1)=f( n-3)因?yàn)榈趎年要比n-1年多的牛，都是大于三歲的牛生的小牛，而 那些在n年大于三歲的牛，然后它們?cè)诘趎年生下相同數(shù)量的小牛。lease injiut )IDUnan9 years it past:IB ou典典u have 1? cattle now!lease input how many yea

11、rs it pdst：12 owyouhiyellcattlejiow!源代碼如下:#include int cattle( int ct , int n)f(n-3)正是if (n4)return ( ct);elsereturn (cattle( ct , n-1)+cattle( ct , n-3);精品文檔精品文檔運(yùn)行結(jié)果如圖3所示：可見，遞歸函數(shù)的主要優(yōu)點(diǎn)是可以把算法寫的比使用非遞歸函數(shù)時(shí)更清晰更 簡(jiǎn)潔，而且某些問題，特別是與人工智能有關(guān)的問題，更適宜用遞歸方法。遞歸 的另一個(gè)優(yōu)點(diǎn)是，遞歸函數(shù)不會(huì)受到懷疑，較非遞歸函數(shù)而言，某些人更相信遞 歸函數(shù)。編寫遞歸函數(shù)時(shí)，必須在函數(shù)的某些地方使用if語(yǔ)句，強(qiáng)迫函數(shù)在未執(zhí) 行遞歸調(diào)用前返回。如果不這樣做，在調(diào)用函數(shù)后，它永遠(yuǎn)不會(huì)返回，造成無(wú)窮 遞歸。在遞歸函數(shù)中不使用if語(yǔ)句，是一個(gè)很常見的錯(cuò)誤。此外，象漢諾塔問題 就只能靠遞歸才能解決，但是現(xiàn)實(shí)中很多問題都是比較簡(jiǎn)單的， 沒有象漢諾塔那 么復(fù)雜，我