[學(xué)習(xí)]算法設(shè)計(jì)與分析—遞歸算法

1、第6章 遞歸算法,1,6.1 遞歸的概念6.2 遞歸算法的執(zhí)行過(guò)程6.3 遞歸算法的設(shè)計(jì)方法6.4 遞歸過(guò)程和運(yùn)行時(shí)棧6.5 遞歸算法的效率分析6.6 遞歸算法到非遞歸算法的轉(zhuǎn)換6.7 設(shè)計(jì)舉例,6.1遞歸的概念,一、在日常生活中，遞歸一詞較常用于描述以自相似方法重復(fù)事物的過(guò)程。例如，當(dāng)兩面鏡子相互之間近似平行時(shí)，鏡中嵌套的圖像是以無(wú)限遞歸的形式出現(xiàn)的。,2,德羅斯特效應(yīng)（英語(yǔ)：Droste effect）是遞歸的一

2、種視覺(jué)形式。圖中女性手持的物體中有一幅她本人手持同一物體的小圖片，進(jìn)而小圖片中還有更小的一幅她手持同一物體的圖片，依此類推。,3,二、在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸是指在函數(shù)的定義中使用函數(shù)自身的方法。例：第5個(gè)人的年齡比第4個(gè)的年齡大2歲，有4個(gè)人的年齡比第3個(gè)的年齡大2歲，有3個(gè)人的年齡比第2個(gè)的年齡大2歲，有2個(gè)人的年齡比第1個(gè)的年齡大2歲，第1個(gè)的年齡10歲。,4,例：階乘的定義。,5,6,在下面二種情況中存在算法調(diào)用自己的情況

3、：,（1）問(wèn)題的定義是遞推的,階乘函數(shù)的常見(jiàn)定義是：,,7,也可定義為：,寫成函數(shù)形式，則為：,這種函數(shù)定義的方法是用階乘函數(shù)自己本身定義了階乘函數(shù)，稱上式為階乘函數(shù)的遞推定義式。,,8,（2）問(wèn)題的解法存在自調(diào)用,一個(gè)典型的例子是在有序數(shù)組中查找一個(gè)數(shù)據(jù)元素是否存在的折半查找算法。 如下例中查找元素17。,,mid=(low+high)/2,9,6.2遞歸算法的執(zhí)行過(guò)程,例6-1 給出按照階乘函數(shù)的遞推定義式計(jì)算階乘函數(shù)的遞歸算法，并

4、給出n = 3時(shí)遞歸算法的執(zhí)行過(guò)程。 設(shè)計(jì)：按照階乘函數(shù)的遞推定義式計(jì)算階乘函數(shù)的遞歸算法如下：,long int Fact(int n){ int x; long int y; if(n < 0) //n < 0時(shí)階乘無(wú)定義 { printf(“參數(shù)錯(cuò)！”); r

5、eturn -1; }  if(n == 0) return 1; else { y = Fact(n - 1); //遞歸調(diào)用 return n * y; }},10,為說(shuō)明該遞歸算法的執(zhí)行過(guò)程，設(shè)計(jì)調(diào)用過(guò)程如下：,void main(void){

6、 long int fn;  fn = Fact(3);},上述代碼用實(shí)參n = 3調(diào)用了遞歸算法Fact(3)，而Fact(3)要通過(guò)調(diào)用Fact(2)、Fact(2)要通過(guò)調(diào)用Fact(1)、Fact(1)要通過(guò)調(diào)用Fact(0)來(lái)得出計(jì)算結(jié)果。Fact(3)的遞歸調(diào)用過(guò)程如下圖所示，其中，黑色實(shí)線箭頭表示函數(shù)調(diào)用，綠色虛線箭頭表示函數(shù)返回，此函數(shù)在返回時(shí)函數(shù)名將帶回返回值。,11,main()

7、 …… fn=Fact(3) ……,Fact (3) …… y=Fact (2) ……return 3*y,Fact (2) …… y=Fact(1) ……return 2*y,,,,,,,,,,,,遞歸調(diào)用的執(zhí)行過(guò)程：,Fact (1) …… y=Fact(0) ……return 1*y,Fact (0) …… ……r

8、eturn 1,,,,,,,,12,例6-2 給出在有序數(shù)組a中查找數(shù)據(jù)元素x是否存在的遞歸算法，并給出折半查找示意圖所示實(shí)際數(shù)據(jù)的遞歸算法的執(zhí)行過(guò)程?！　≡O(shè)計(jì)：算法的參數(shù)包括：有序數(shù)組a，要查找的數(shù)據(jù)元素x，數(shù)組下界下標(biāo)low，數(shù)組上界下標(biāo)high。當(dāng)在數(shù)組a中查找到數(shù)據(jù)元素x時(shí)函數(shù)返回?cái)?shù)組a的下標(biāo)；當(dāng)在數(shù)組a中查找不到數(shù)據(jù)元素x時(shí)函數(shù)返回-1。,13,遞歸算法如下：,int BSearch(int a[], int x, int

9、low, int high){ int mid;if(low > high) return -1;　　　//查找不成功 mid = (low + high) / 2;if(x == a[mid])return mid;//查找成功else if(x < a[mid]) return BSearch(a, x, low, mid-1);//在下半?yún)^(qū)查找elsereturn B

10、Search(a, x, mid+1, high);//在上半?yún)^(qū)查找},14,測(cè)試代碼設(shè)計(jì)如下：# include  main(void){ int a[] = {1, 3, 4, 5, 17, 18, 31, 33}; int x = 17; int bn;  bn = BSearch(a, x, 0,7); i

11、f(bn == -1) printf("x不在數(shù)組a中"); else printf("x在數(shù)組a的下標(biāo)%d中", bn);},15,BSearch(a, x, 0,7)的遞歸調(diào)用過(guò)程如下圖所示，其中，實(shí)箭頭表示過(guò)程調(diào)用，虛箭頭表示過(guò)程的返回值。,BSearch(a, x, 0, 7) … mid=3 …return BSearch(a, x, 4, 7),

12、main() … x=17 … bn = BSearch(a, x, 0, 7),BSearch(a, x, 4, 7) … mid=5 …return BSearch(a, x, 4, 4),BSearch(a, x, 4, 4) … mid=4 …return 4,,,,16,6.3遞歸算法的設(shè)計(jì)方法,,遞歸算法既是一種有效的算法設(shè)計(jì)方法，也是一種有效的分析問(wèn)題的方法。

13、遞歸算法求解問(wèn)題的基本思想是：對(duì)于一個(gè)較為復(fù)雜的問(wèn)題，把原問(wèn)題分解成若干個(gè)相對(duì)簡(jiǎn)單且類同的子問(wèn)題，這樣較為復(fù)雜的原問(wèn)題就變成了相對(duì)簡(jiǎn)單的子問(wèn)題；而簡(jiǎn)單到一定程度的子問(wèn)題可以直接求解；這樣，原問(wèn)題就可遞推得到解。,17,,并不是每個(gè)問(wèn)題都適宜于用遞歸算法求解。適宜于用遞歸算法求解的問(wèn)題的充分必要條件是：（1）問(wèn)題具有某種可借用的類同自身的子問(wèn)題描述的性質(zhì)；（2）某一有限步的子問(wèn)題（也稱作本原問(wèn)題）有直接的解存在。,18,,當(dāng)一個(gè)問(wèn)題存

14、在上述兩個(gè)基本要素時(shí)，設(shè)計(jì)該問(wèn)題的遞歸算法的方法是：（1）把對(duì)原問(wèn)題的求解設(shè)計(jì)成包含有對(duì)子問(wèn)題求解的形式。（2）設(shè)計(jì)遞歸出口。,19,例6-3 設(shè)計(jì)模擬漢諾塔問(wèn)題求解過(guò)程的算法。漢諾塔問(wèn)題的描述是：設(shè)有3根標(biāo)號(hào)為A，B，C的柱子，在A柱上放著n個(gè)盤子，每一個(gè)都比下面的略小一點(diǎn)，要求把A柱上的盤子全部移到C柱上，移動(dòng)的規(guī)則是：（1）一次只能移動(dòng)一個(gè)盤子；（2）移動(dòng)過(guò)程中大盤子不能放在小盤子上面；（3）在移動(dòng)過(guò)程中盤子可以放在A，B，C

15、的任意一個(gè)柱子上?！　?wèn)題分析：可以用遞歸方法求解n個(gè)盤子的漢諾塔問(wèn)題。,20,基本思想：1個(gè)盤子的漢諾塔問(wèn)題可直接移動(dòng)。n個(gè)盤子的漢諾塔問(wèn)題可遞歸表示為，首先把上邊的n-1個(gè)盤子從A柱移到B柱，然后把最下邊的一個(gè)盤子從A柱移到C柱，最后把移到B柱的n-1個(gè)盤子再移到C柱。4個(gè)盤子漢諾塔問(wèn)題的遞歸求解示意圖如下圖所示。,21,,,,,原柱 A 輔助柱 B

16、 目標(biāo)柱 C,22,算法設(shè)計(jì)：首先，盤子的個(gè)數(shù)n是必須的一個(gè)輸入?yún)?shù)，對(duì)n個(gè)盤子,我們可從上至下依次編號(hào)為1,2,…,n；其次，輸入?yún)?shù)還需有3個(gè)柱子的代號(hào),我們令3個(gè)柱子的參數(shù)名分別為fromPeg，auxPeg和toPeg；最后，漢諾塔問(wèn)題的求解是一個(gè)處理過(guò)程，因此算法的輸出是n個(gè)盤子從柱子fromPeg借助柱子auxPeg移動(dòng)到柱子toPeg的移動(dòng)步驟，我們?cè)O(shè)計(jì)每一步的移動(dòng)為屏幕顯示如下形式的信息：Move Di

17、sk i from Peg X to Peg Y這樣，漢諾塔問(wèn)題的遞歸算法可設(shè)計(jì)如下：,23,void towers(int n, char fromPeg, char toPeg, char auxPeg){ if(n==1)//遞歸出口 { printf("%s%c%s%c\n", "move disk 1 from peg ",

18、 fromPeg, " to peg ", toPeg); return; } 　 //把n-1個(gè)圓盤從fromPeg借助toPeg移至auxPeg towers(n-1,fromPeg,auxPeg,toPeg);  //把圓盤n由fromPeg直接移至toPeg printf(&quo

19、t;%s%d%s%c%s%c\n", "move disk ", n, " from peg ", fromPeg, " to peg ", toPeg);  //把n-1個(gè)圓盤從auxPeg借助fromPeg移至toPeg towers(n-1,auxPeg,toPeg,

20、fromPeg);},24,測(cè)試代碼如下：#include  void main(void){ Towers(4, 'A', 'C', 'B');}程序運(yùn)行的輸出信息如下：,25,Move Disk 1 from Peg A to Peg BMove Disk 2 from Peg A to Peg CMove Disk 1 from Pe

21、g B to Peg CMove Disk 3 from Peg A to Peg BMove Disk 1 from Peg C to Peg AMove Disk 2 from Peg C to Peg BMove Disk 1 from Peg A to Peg BMove Disk 4 from Peg A to Peg CMove Disk 1 from Peg B to Peg CMove Disk 2 fro

22、m Peg B to Peg AMove Disk 1 from Peg C to Peg AMove Disk 3 from Peg B to Peg CMove Disk 1 from Peg A to Peg BMove Disk 2 from Peg A to Peg CMove Disk 1 from Peg B to Peg C,26,結(jié)合本節(jié)和6.2節(jié)的討論，我們可總結(jié)如下：遞歸算法的執(zhí)行過(guò)程是不斷地自調(diào)用，直到

23、到達(dá)遞歸出口才結(jié)束自調(diào)用過(guò)程；到達(dá)遞歸出口后，遞歸算法開(kāi)始按最后調(diào)用的過(guò)程最先返回的次序返回；返回到最外層的調(diào)用語(yǔ)句時(shí)遞歸算法執(zhí)行過(guò)程結(jié)束。,27,6.4遞歸過(guò)程和運(yùn)行時(shí)棧,,對(duì)于非遞歸函數(shù)，調(diào)用函數(shù)在調(diào)用被調(diào)用函數(shù)前，系統(tǒng)要保存以下兩類信息： （1）調(diào)用函數(shù)的返回地址（從而能執(zhí)行下一語(yǔ)句）； （2）調(diào)用函數(shù)的局部變量值。 當(dāng)執(zhí)行完被調(diào)用函數(shù)，返回調(diào)用函數(shù)前，系統(tǒng)首先要恢復(fù)調(diào)用函數(shù)的局部變量值，然后返回調(diào)用函數(shù)的返回

24、地址?！　∵f歸函數(shù)被調(diào)用時(shí)，系統(tǒng)要做的工作和非遞歸函數(shù)被調(diào)用時(shí)系統(tǒng)要作的工作在形式上類同，但保存信息的內(nèi)容和方法不同。,28,保存內(nèi)容：　 每一層遞歸調(diào)用所需要保存的信息構(gòu)成一個(gè)工作記錄，通常包括如下內(nèi)容：    （1）本次遞歸調(diào)用中的局部變量值；     （2）返回地址，即本次遞歸過(guò)程調(diào)用語(yǔ)句的后繼語(yǔ)句的地址；    （3）本次調(diào)用中與

25、形參結(jié)合的實(shí)參值，包括函數(shù)名、引用參數(shù)與數(shù)值參數(shù)等。,工作記錄,,局部變量 返回地址 參 數(shù),,,,,29,,保存方法:　　 遞歸函數(shù)被調(diào)用時(shí)，系統(tǒng)在運(yùn)行遞歸函數(shù)前也要保存上述兩類信息。但因?yàn)檫f歸的函數(shù)的運(yùn)行特點(diǎn)，是最后被調(diào)用的函數(shù)要最先被返回，若按非遞歸函數(shù)那樣保存信息，顯然要出錯(cuò)。 由于堆棧的后進(jìn)先出特性正好與遞歸函數(shù)調(diào)用和返回的過(guò)程吻合，因此，高級(jí)程序設(shè)計(jì)語(yǔ)言利用堆棧保存遞歸函數(shù)調(diào)用的信息，系

26、統(tǒng)用于保存遞歸函數(shù)調(diào)用信息的堆棧稱為運(yùn)行時(shí)棧。,,運(yùn)行時(shí)棧示意圖,棧頂,棧底,30,遞歸函數(shù)被調(diào)用時(shí)，在每進(jìn)入下一層遞歸調(diào)用時(shí)，系統(tǒng)就建立一個(gè)新的工作記錄，并把這個(gè)工作記錄進(jìn)棧成為運(yùn)行時(shí)棧新的棧頂；每返回一層遞歸調(diào)用，就退棧一個(gè)工作記錄。 因?yàn)闂ｍ數(shù)墓ぷ饔涗洷囟ㄊ钱?dāng)前正在運(yùn)行的遞歸函數(shù)的工作記錄，所以棧頂?shù)墓ぷ饔涗浺卜Q為活動(dòng)記錄。,,工作記錄,活動(dòng)記錄,,運(yùn)行時(shí)棧示意圖,棧頂,棧底,我們以計(jì)算階乘的遞歸函數(shù)為例，說(shuō)明遞歸函數(shù)調(diào)用

27、時(shí)運(yùn)行時(shí)棧中工作記錄的變化過(guò)程。,31,long Fact( int n) { int x; long y; If n == 0 return 1; else { x = n-1; y = Fact(x); return n * y; }},由于函數(shù)的地址是系統(tǒng)動(dòng)態(tài)分配的，調(diào)用函數(shù)的返回地址因此也是動(dòng)態(tài)變化的，不好給出具體數(shù)值，故下圖中沒(méi)有給出調(diào)

28、用函數(shù)的返回地址。,32,運(yùn)行時(shí)棧的變化過(guò)程,long Fact( int n) { int x; long y; If n == 0 return 1; else { x = n-1; y = Fact(x); return n * y; }},33,6.5遞歸算法的效率分析,我們先以斐波那契(Fibonacci)數(shù)列遞歸算法的執(zhí)行效率為例來(lái)討

29、論遞歸算法的執(zhí)行效率問(wèn)題。 斐波那契數(shù)列Fib(n)的遞推定義是：如Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(4)=3,Fib(5)=5,…,Fib(n)=,34,求第n項(xiàng)斐波那契數(shù)列的遞歸函數(shù)過(guò)程如下：,long Fib(int n){ if(n == 0 || n == 1) return n; //遞歸出口 else retur

30、n Fib(n-1) + Fib(n-2); //遞歸調(diào)用},35,求Fib(5)的遞歸計(jì)算過(guò)程如圖所示。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(5),斐波那契數(shù)列Fib(5)的遞歸調(diào)用樹(shù),36,為了計(jì)算Fib(5

31、)，需要先計(jì)算Fib(4)和Fib(3)；而計(jì)算Fib(4)又需要計(jì)算Fib(3)（再一次計(jì)算）和Fib(2)，… … . 由上圖可知，為了計(jì)算Fib(5)，需要計(jì)算1次Fib(4)，2次Fib(3)，3次Fib(2)，5次Fib(1)，3次Fib(0). 加上Fib(5)1次，所有的遞歸調(diào)用次數(shù)達(dá)到15次。（圖中15個(gè)點(diǎn)表示15次運(yùn)算） 更一般地，設(shè)Fib(n)需要總的遞歸調(diào)用次數(shù)為NumCall(n)，

32、那么NumCall(n)等于多少？,NumCall(n)= NumCall(n-1)+ NumCall(n-2)+1NumCall(0)=1, NumCall(1)=1 可以求得NumCall的通項(xiàng)。也可以由下面的關(guān)系得到NumCall的通項(xiàng)。NumCall(n) = 2*Fib(n+1) - 1。 可以證明，計(jì)算斐波那契數(shù)列的遞歸函數(shù)Fib(n)的時(shí)間復(fù)雜度為O(2n)。,37,,計(jì)算斐波那契數(shù)列

33、Fib(n)問(wèn)題，我們也可根據(jù)公式寫出循環(huán)方式求解的函數(shù)如下：,38,39,long Fib2(int n){ long int oneBack, twoBack, current; int i;  if(n == 0 || n == 1) return n; else { oneBack = 1;

34、twoBack = 0; for(i = 2; i <= n; i++) { current = oneBack + twoBack; twoBack = oneBack; oneBack = current; } return current;}},40,上述循環(huán)方式的計(jì)算斐波那契數(shù)列的函數(shù)Fib2(n)的時(shí)間復(fù)雜度為O(n)。對(duì)

35、比循環(huán)結(jié)構(gòu)的Fib2(n)和遞歸結(jié)構(gòu)的Fib(n)可發(fā)現(xiàn): 循環(huán)結(jié)構(gòu)的Fib2(n)算法在計(jì)算第n項(xiàng)的斐波那契數(shù)列時(shí)保存了當(dāng)前已經(jīng)計(jì)算得到的第n-1項(xiàng)和第n-2項(xiàng)的斐波那契數(shù)列，因此其時(shí)間復(fù)雜度為O(n)； 而遞歸結(jié)構(gòu)的Fib(n)算法在計(jì)算第n項(xiàng)的斐波那契數(shù)列時(shí)，必須首先計(jì)算第n-1項(xiàng)和第n-2項(xiàng)的斐波那契數(shù)列，而某次遞歸計(jì)算得出的斐波那契數(shù)列，如Fib(n-1)、Fib(n-2)等無(wú)法保存，下一次要用到

36、時(shí)還需要重新遞歸計(jì)算，因此其時(shí)間復(fù)雜度為O(2n) 。,下面我們?cè)倏纯礉h諾塔的時(shí)間復(fù)雜度。設(shè)移動(dòng)n個(gè)盤子的步數(shù)為H(n)，我們?cè)倏纯词疽鈭D。,41,42,,,,,這一步實(shí)際有H(n-1)步,這只需1步,這一步又需要H(n-1)步,故移動(dòng)n個(gè)圓盤的總步數(shù)H(n)=H(n-1)+1+H(n-1) =2H(n-1)+1,原柱

37、 A 輔助柱 B 目標(biāo)柱 C,即有 H(n)=2H(n-1)+1 S(1)=1可以解得：H(n)=2n-1因此漢諾塔的時(shí)間復(fù)雜度為O(2n) 。,43,,44,6.6遞歸算法到非遞歸算法的轉(zhuǎn)換,有些問(wèn)題需要用低級(jí)程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)，而低級(jí)程序設(shè)計(jì)語(yǔ)言（如匯編語(yǔ)言）一般不支持遞歸，此

38、時(shí)需要采用問(wèn)題的非遞歸結(jié)構(gòu)算法。一般來(lái)說(shuō)，存在如下兩種情況的遞歸算法。 （1）存在不借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，如階乘計(jì)算問(wèn)題、斐波那契數(shù)列的計(jì)算問(wèn)題、折半查找問(wèn)題等。 （2）存在借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，所有遞歸算法都可以借助堆棧轉(zhuǎn)換成循環(huán)結(jié)構(gòu)的非遞歸算法，如漢諾塔問(wèn)題可以借助堆棧的循環(huán)結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法。,45,對(duì)于第一種情況，可以直接選用循環(huán)結(jié)構(gòu)的算法。 對(duì)于第二種情況，可以把遞歸算法轉(zhuǎn)換成相應(yīng)的非遞歸算法，

39、此時(shí)有兩種轉(zhuǎn)換方法：一種方法是借助堆棧，用非遞歸算法形式化模擬遞歸算法的執(zhí)行過(guò)程；另一種方法是根據(jù)要求解問(wèn)題的特點(diǎn)，設(shè)計(jì)借助堆棧的循環(huán)結(jié)構(gòu)算法。這兩種方法都需要使用堆棧，這是因?yàn)槎褩５暮筮M(jìn)先出特點(diǎn)正好和遞歸函數(shù)的運(yùn)行特點(diǎn)相吻合。 通常，一個(gè)遞歸算法的模擬算法的復(fù)雜度與其本身的復(fù)雜度一樣。,46,例6-6 借助堆棧模擬系統(tǒng)的運(yùn)行時(shí)進(jìn)棧、出棧過(guò)程，把漢諾塔問(wèn)題的遞歸算法轉(zhuǎn)化為非遞歸算法，并分析非遞歸算法的時(shí)間復(fù)雜度。,47,6.7設(shè)

40、計(jì)舉例,6.7.1 一般遞歸算法設(shè)計(jì)舉例,例6-5 設(shè)計(jì)一個(gè)輸出如下形式數(shù)值的遞歸算法。n n n ... n...... 3 3 3 2 21,48,問(wèn)題分析：該問(wèn)題可以看成由兩部分組成：一部分是輸出一行值為n的數(shù)值；另一部分是原問(wèn)題的子問(wèn)題，其參數(shù)為n-1。當(dāng)參數(shù)減到0時(shí)不再輸出任何數(shù)據(jù)值，因此遞歸的出口是當(dāng)參數(shù)n≤0時(shí)空語(yǔ)句返回。 void Display(int n)

41、 { int i;  for(i = 1; i 0) Display(n - 1);//遞歸  //n<=0為遞歸出口，遞歸出口為空語(yǔ)句 },49,例6-6 設(shè)計(jì)求解委員會(huì)問(wèn)題的算法。委員會(huì)問(wèn)題是：從一個(gè)有n個(gè)人的團(tuán)體中抽出k (k≤n)個(gè)人組成一個(gè)委員會(huì)，計(jì)算共有多少種構(gòu)成方法。問(wèn)題分析：從n個(gè)人中抽出k(k≤n)個(gè)人的問(wèn)題是一個(gè)組合

42、問(wèn)題。即求組合數(shù)公式C(n,k)。由于要所用遞歸算法,大家容易想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k),這個(gè)公式大家可以這樣理解:把n個(gè)人固定位置后，從n個(gè)人中抽出k個(gè)人的問(wèn)題可分解為兩部分之和：第一部分是第一個(gè)人包括在k個(gè)人中，第二部分是第一個(gè)人不包括在k個(gè)人中。對(duì)于第一部分，則問(wèn)題簡(jiǎn)化為從n-1個(gè)人中抽出k-1個(gè)人的問(wèn)題；對(duì)于第二部分，則問(wèn)題簡(jiǎn)化為從n-1個(gè)人中抽出k個(gè)人的問(wèn)題。,50,當(dāng)n=k或k=0時(shí)，該

43、問(wèn)題可直接求解，數(shù)值均為1，這是算法的遞歸出口。因此，委員會(huì)問(wèn)題的遞推定義式為：,int Comm(int n, int k){ if(n n) return 0;  if(k == 0) return 1; if(n == k) return 1; return Comm(n-1, k-1) + Comm(n-1, k); },51,

44、例6-7 求兩個(gè)正整數(shù)n和m最大公約數(shù)的遞推定義式為：,要求： （1）編寫求解該問(wèn)題的遞歸算法； （2）分析當(dāng)調(diào)用語(yǔ)句為Gcd(30, 4)時(shí)算法的執(zhí)行過(guò)程和執(zhí)行結(jié)果； （3）分析當(dāng)調(diào)用語(yǔ)句為Gcd(5, 97)時(shí)算法的執(zhí)行過(guò)程和執(zhí)行結(jié)果； （4）編寫求解該問(wèn)題的循環(huán)結(jié)構(gòu)算法。,52,解：（1）遞歸算法如下： int Gcd(int n, int m) { if(n n) return Gcd

45、(m, n); else return Gcd(m, n % m); },53,（2）調(diào)用語(yǔ)句為Gcd(30, 4)時(shí)，因mn，遞歸調(diào)用Gcd(97, 5)；因m<n，遞歸調(diào)用Gcd(5, 2)；因m<n，遞歸調(diào)用Gcd(2, 1)；因m<n，遞歸調(diào)用Gcd(1, 0)；因m=0，到達(dá)遞歸出口，函數(shù)最終返回值為n=1，即5和97的最大公約數(shù)為1。,（4）循環(huán)結(jié)構(gòu)算

46、法int Gcd2(int n, int m) { int tn, tm, temp; if (n n) { tn = m; tm = n; }else { tn = n; tm = m; } While tm != 0 { temp = tn; tn = tm; tm = temp %

47、 tm;} return tn;},54,55,6.7.2 回溯法及其設(shè)計(jì)舉例,回溯法是遞歸算法的一種特殊形式，回溯法的基本思想是：對(duì)一個(gè)包括有很多結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有若干個(gè)搜索分支的問(wèn)題，把原問(wèn)題分解為對(duì)若干個(gè)子問(wèn)題求解的算法。當(dāng)搜索到某個(gè)結(jié)點(diǎn)、發(fā)現(xiàn)無(wú)法再繼續(xù)搜索下去時(shí)，就讓搜索過(guò)程回溯退到該結(jié)點(diǎn)的前一結(jié)點(diǎn)，繼續(xù)搜索這個(gè)結(jié)點(diǎn)的其他尚未搜索過(guò)的分支；如果發(fā)現(xiàn)這個(gè)結(jié)點(diǎn)也無(wú)法再繼續(xù)搜索下去時(shí)，就讓搜索過(guò)程回溯（即退回）到這個(gè)結(jié)點(diǎn)的前一