遞歸程序設(shè)計

1、4.6遞歸程序設(shè)計11.遞歸函數(shù)一個函數(shù)被調(diào)用，在尚未執(zhí)行完之前，又直接或間接地調(diào)用了這個函數(shù)本身，這樣的函數(shù)稱遞歸函數(shù)。遞歸函數(shù)分為直接遞歸函數(shù)和間接遞歸函數(shù)。這種函數(shù)的示意圖如下：231)直接遞歸函數(shù)如果一個函數(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ù)如果一個函數(shù)通過在其定義中調(diào)用其它函數(shù)，再由其它函數(shù)調(diào)用該函數(shù)，稱這種函數(shù)為間接遞歸函數(shù)。6比如下面的代碼定義

2、了兩個函數(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()各自實現(xiàn)了間接遞歸調(diào)用自己。72.簡單遞歸函數(shù)舉例 已知Fibonacci序列的數(shù)學(xué)定義如下： 使用遞歸程序計算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ù)的特點1)至少存在一個基本解(不再遞歸)。2)每一次求解過程都可歸結(jié)為把對一個較大較為復(fù)雜的問題的求解轉(zhuǎn)化為對較為小較為簡單的同類問題的求解。3)經(jīng)過執(zhí)行有限步之后，總能達到

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

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

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

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

8、(frompeg)移到C(topeg)；把B柱(auxiliary/temppeg)上的n-1個盤子借助A柱(frompeg)移到C柱(to/topeg)。函數(shù)可設(shè)計為：move_tower(盤個數(shù)，取出柱，放入柱，輔助柱)18以上三點為基本思想，則歸納的n個盤子的移動(n1)函數(shù)如下： move_tower(int disk_num, char from, char to , char aux); 注: from-frompeg to-topeg aux-auxiliary或temporary 它可以通過求move_tower(disk_num-1,from,aux,to);和mov_tower(disk_num-1,aux,to,from);來實現(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