遞歸程序設(shè)計(jì)

1、4.6遞歸程序設(shè)計(jì)11.遞歸函數(shù)一個(gè)函數(shù)被調(diào)用，在尚未執(zhí)行完之前，又直接或間接地調(diào)用了這個(gè)函數(shù)本身，這樣的函數(shù)稱遞歸函數(shù)。遞歸函數(shù)分為直接遞歸函數(shù)和間接遞歸函數(shù)。這種函數(shù)的示意圖如下：231)直接遞歸函數(shù)如果一個(gè)函數(shù)在其定義中直接調(diào)用自己，則稱這種函數(shù)為直接遞歸函數(shù)。4比如下面函數(shù)求n的階乘，采用的是直接遞歸調(diào)用形式，因此是直接遞歸函數(shù)： long factorial(int n) if(n=0) return 1; return factorial(n-1)*n; 52）間接遞歸函數(shù)如果一個(gè)函數(shù)通過(guò)在其定義中調(diào)用其它函數(shù)，再由其它函數(shù)調(diào)用該函數(shù)，稱這種函數(shù)為間接遞歸函數(shù)。6比如下面的代碼定義

2、了兩個(gè)函數(shù)，它們構(gòu)成了間接遞歸調(diào)用：int f1(int a) int b; b=f2(a+1); /間接遞歸調(diào)用 ：f1()調(diào)用了f2() /.int f2(int a) int c; c=f1(s-1); /間接遞歸調(diào)用 ：f2()又調(diào)用了f1() /.在上面代碼中，f1()調(diào)用了f2()，而f2()又調(diào)用了f1()，這樣f1()、f2()各自實(shí)現(xiàn)了間接遞歸調(diào)用自己。72.簡(jiǎn)單遞歸函數(shù)舉例 已知Fibonacci序列的數(shù)學(xué)定義如下： 使用遞歸程序計(jì)算Fibonacci數(shù)序列。8分析如下： 設(shè)n為5，則有： F(5)=F(3)+F(4) =F(1)+F(2)+F(2)+F(3) =F(1)+

3、F(0)+F(1)+F(0)+F(1)+F(1)+F(2) =F(1)+F(0)+F(1)+F(0)+F(1)+F(1)+F(0)+F(1) =1+1+1+1+1+1+1+1 =89因此可以歸納為函數(shù)：int fibonacci(int n) /n是大于等于0 的整數(shù) if(n=0)|(n=1) return 1; if(n1) return (fibonacci(n-2)+fibonacci(n-1); 103.遞歸函數(shù)的特點(diǎn)1)至少存在一個(gè)基本解(不再遞歸)。2)每一次求解過(guò)程都可歸結(jié)為把對(duì)一個(gè)較大較為復(fù)雜的問(wèn)題的求解轉(zhuǎn)化為對(duì)較為小較為簡(jiǎn)單的同類問(wèn)題的求解。3)經(jīng)過(guò)執(zhí)行有限步之后，總能達(dá)到

4、基本解。11從求Fibonacci序列的例子分析遞歸函數(shù)的三大特點(diǎn)：121)n=0和n=1時(shí)是基本解，此時(shí)函數(shù)不用再遞歸，可以直接得出結(jié)果，即f(0)=1,f(1)=1。2)當(dāng)n1時(shí)，f(n)總是可以通過(guò)轉(zhuǎn)化為求f(n-1)和f(n-2)來(lái)實(shí)現(xiàn),即f(n)=f(n-1)+f(n-2)。求f(n-1)、f(n-2)是和求f(n)同類的但較小較簡(jiǎn)單的問(wèn)題。133)不論n多大，總能轉(zhuǎn)化為求f(n-1)和f(n-2)來(lái)實(shí)現(xiàn)，而f(n-1)和f(n-2)又各自可以轉(zhuǎn)化為較小較簡(jiǎn)單的問(wèn)題，這樣經(jīng)過(guò)有限步后，總可以達(dá)到基本解，即轉(zhuǎn)化為求f(0)和f(1)來(lái)實(shí)現(xiàn)。當(dāng)然n可以無(wú)限大只是理論上的，實(shí)際上n的大小還

5、得受計(jì)算機(jī)可表示的范圍限制，即n及其結(jié)果f(n)必須在int類型能表達(dá)的范圍之內(nèi)。把類型int改成long可以相應(yīng)增大n的范圍。144.漢諾塔問(wèn)題1)問(wèn)題描述：傳說(shuō)在19世紀(jì)末，Bramah神廟的教士玩一種稱為梵塔(Tower of Hanoi)的游戲：共有三個(gè)柱子以及有n(n0)個(gè)能套進(jìn)柱子的大小不一的盤(pán)子，盤(pán)按從小到大的順序標(biāo)號(hào)為1到n.開(kāi)始時(shí)n個(gè)盤(pán)子均套在A柱上，且小的放在大的上面(如下圖所示)。游戲要求按下列規(guī)則將所有的盤(pán)從A柱移到C柱，在移動(dòng)過(guò)程中可以借助另一個(gè)B柱。規(guī)則1:每次只能移動(dòng)柱最上面的一個(gè)盤(pán)子；規(guī)則2：任何時(shí)候都不可以把大的盤(pán)子放到小的盤(pán)子上。152)先從簡(jiǎn)單問(wèn)題著手：當(dāng)

6、n等于1時(shí)；移動(dòng)1次(21-1次)當(dāng)n等于2時(shí);移動(dòng)3次(22-1次) A-B A-C B-C當(dāng)n等于3時(shí)；移動(dòng)7次(23-1次) A-C A-B C-B A-C B-A B-C A-C當(dāng)n為4時(shí)，移動(dòng)24-1=15次當(dāng)n為5時(shí)，移動(dòng)25-1=31次 從而合理推測(cè)：當(dāng)n為k時(shí)，移動(dòng)2k-1次當(dāng)n等于64時(shí)，移動(dòng)次數(shù)為264-1次16 按照漢諾塔的移動(dòng)原則，將N個(gè)盤(pán)從A桿移動(dòng)到C 桿需要移動(dòng)盤(pán)的次數(shù)是 2 的 N 次冪減 1 ， 那么 64個(gè)盤(pán)移動(dòng)次數(shù)就是184467445，近19億億次（且沒(méi)有任何錯(cuò)誤操作。這是一個(gè)天文數(shù)字，即使一臺(tái)功能很強(qiáng)的現(xiàn)代計(jì)算機(jī)來(lái)解漢諾塔問(wèn)題，恐怕也需要很長(zhǎng)的時(shí)間，因此

7、要想得到結(jié)果，在運(yùn)行程序時(shí)，輸入的N可不能太大。據(jù)說(shuō)布拉瑪婆羅門(mén)圣廟的僧侶聲稱， 漢諾塔游戲結(jié)束就標(biāo)志著世界末日的到來(lái)，現(xiàn)在看來(lái)確實(shí)是有道理的。因?yàn)槿绻棵胍苿?dòng)一次（且沒(méi)有任何錯(cuò)誤），64個(gè)盤(pán)則大約需近5800億年，而據(jù)科學(xué)家以能源角度推算，太陽(yáng)系的壽命只不過(guò)150 億年而已。 173）分析及解答執(zhí)行條件：只要n0(n是整數(shù)),我們就要執(zhí)行。如果n為1(只有一個(gè)盤(pán)子)，很易辦到，只要frompeg-topeg。把在A柱上(frompeg)上的n-1(n1)個(gè)盤(pán)子依規(guī)則從A(frompeg)柱移到B柱上(auxiliary/temppeg)可借助空柱C(to/topeg);把A柱上剩下的1個(gè)從A

8、(frompeg)移到C(topeg)；把B柱(auxiliary/temppeg)上的n-1個(gè)盤(pán)子借助A柱(frompeg)移到C柱(to/topeg)。函數(shù)可設(shè)計(jì)為：move_tower(盤(pán)個(gè)數(shù)，取出柱，放入柱，輔助柱)18以上三點(diǎn)為基本思想，則歸納的n個(gè)盤(pán)子的移動(dòng)(n1)函數(shù)如下： move_tower(int disk_num, char from, char to , char aux); 注: from-frompeg to-topeg aux-auxiliary或temporary 它可以通過(guò)求move_tower(disk_num-1,from,aux,to);和mov_tower(disk_num-1,aux,to,from);來(lái)實(shí)現(xiàn)。19源程序如下：includevoid move_tower(int disk_num,char from,char to ,char aux) if(disk_num1) mov_tower(disk_num-1,from,aux,to); coutMove disk disk_numfromfromtotoendl; move_tower(disk_num-1,aux,to,from); else coutMove disk 1 fr