《《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》-第06章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》-第06章.ppt（42頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1,第6章 遞歸算法,遞歸的概念 遞歸算法的執(zhí)行過(guò)程 遞歸算法的設(shè)計(jì)方法 遞歸過(guò)程和運(yùn)行時(shí)棧 遞歸算法的效率分析 設(shè)計(jì)舉例,主要知識(shí)點(diǎn),,2,存在算法調(diào)用自己的情況：,若一個(gè)算法直接的或間接的調(diào)用自己本身，則稱這個(gè)算法是遞歸算法。,（1）問(wèn)題的定義是遞推的,,階乘函數(shù)的常見(jiàn)定義是：,6.1遞歸的概念,,3,也可定義為：,寫成函數(shù)形式，則為：,這種函數(shù)定義的方法是用階乘函數(shù)自己本身定義了階乘函數(shù)，稱公式（6 3）是階乘函數(shù)的遞推定義式。,,4,（2）問(wèn)題的解法存在自調(diào)用,一個(gè)典型的例子是在有序數(shù)組中查找一個(gè)數(shù)據(jù)元素是否存在的折半查找算法。,,5,圖6-1 折半查找過(guò)程,6,6.2遞歸算法的執(zhí)行過(guò)

2、程,例6-1 給出按照公式6-3計(jì)算階乘函數(shù)的遞歸算法，并給出n = 3時(shí)遞歸算法的執(zhí)行過(guò)程。 設(shè)計(jì)：按照公式6-3計(jì)算階乘函數(shù)的遞歸算法如下：,7,long int Fact(int n) int x; long int y; if(n < 0) //n < 0時(shí)階乘無(wú)定義 printf(“參數(shù)錯(cuò)！”); return -1; if(n == 0) return 1; else y = Fact(n - 1); //遞歸調(diào)用 return n * y; ,8,設(shè)計(jì)主函數(shù)如下,void main(void) long i

3、nt fn; fn = Fact(3); ,主函數(shù)用實(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ò)程如圖6-2所示。,9,圖6-2 Fact(3)的遞歸調(diào)用執(zhí)行過(guò)程,10,,例6-2 給出在有序數(shù)組a中查找數(shù)據(jù)元素x是否存在的遞歸算法，并給出如圖6-1所示實(shí)際數(shù)據(jù)的遞歸算法的執(zhí)行過(guò)程。遞歸算法如下：,11,int BSearch(int a, int x, int low, int high) int mid; if(low high

4、) return -1;//查找不成功 mid = (low + high) / 2; if(x == amid)return mid;//查找成功 else if(x < amid) return BSearch(a, x, low, mid-1);//在下半?yún)^(qū)查找 else return BSearch(a, x, mid+1, high);//在上半?yún)^(qū)查找 ,12,測(cè)試主函數(shù)設(shè)計(jì)如下： # include main(void) int a = 1, 3, 4, 5, 17, 18, 31, 33; int x = 17; int bn; bn = BSearch(a, x

5、, 0,7); if(bn == -1) printf(x不在數(shù)組a中); else printf(x在數(shù)組a的下標(biāo)%d中, bn); ,13,BSearch(a, x, 0,7)的遞歸調(diào)用過(guò)程如圖6-3所示，其中，實(shí)箭頭表示函數(shù)調(diào)用，虛箭頭表示函數(shù)的返回值。,圖6-3 BSearch(a, x, 0,7)的遞歸調(diào)用過(guò)程,14,15,6.3遞歸算法的設(shè)計(jì)方法,,遞歸算法既是一種有效的算法設(shè)計(jì)方法，也是一種有效的分析問(wèn)題的方法。 遞歸算法求解問(wèn)題的基本思想是：對(duì)于一個(gè)較為復(fù)雜的問(wèn)題，把原問(wèn)題分解成若干個(gè)相對(duì)簡(jiǎn)單且類同的子問(wèn)題,這樣，原問(wèn)題就可遞推得到解。,16,適宜于用遞歸算法求解的問(wèn)

6、題的充分必要條件是： （1）問(wèn)題具有某種可借用的類同自身的子問(wèn)題描述的性質(zhì)； （2）某一有限步的子問(wèn)題（也稱作本原問(wèn)題）有直接的解存在。 當(dāng)一個(gè)問(wèn)題存在上述兩個(gè)基本要素時(shí)，該問(wèn)題的遞歸算法的設(shè)計(jì)方法是： （1）把對(duì)原問(wèn)題的求解設(shè)計(jì)成包含有對(duì)子問(wèn)題求解的形式。 （2）設(shè)計(jì)遞歸出口。,17,例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

7、，C的任意一個(gè)柱子上。,18,問(wèn)題分析： 可以用遞歸方法求解n個(gè)盤子的漢諾塔問(wèn)題。 基本思想： 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)題的遞歸求解示意圖如圖6-4所示。,19,圖6-4 漢諾塔問(wèn)題的遞歸求解示意圖,20,算法設(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；

8、最后，漢諾塔問(wèn)題的求解是一個(gè)處理過(guò)程，因此算法的輸出是n個(gè)盤子從柱子fromPeg借助柱子auxPeg移動(dòng)到柱子toPeg的移動(dòng)步驟，我們?cè)O(shè)計(jì)每一步的移動(dòng)為屏幕顯示如下形式的信息： Move Disk i from Peg X to Peg Y 這樣，漢諾塔問(wèn)題的遞歸算法可設(shè)計(jì)如下：,21,void towers(int n, char fromPeg, char toPeg, char auxPeg) if(n==1)//遞歸出口 printf(%s%c%s%cn, move disk 1 from peg , fromPeg, to peg , toPeg); ret

9、urn; //把n-1個(gè)圓盤從fromPeg借助toPeg移至auxPeg towers(n-1,fromPeg,auxPeg,toPeg); //把圓盤n由fromPeg直接移至toPeg printf(%s%d%s%c%s%cn, move disk , n, from peg , fromPeg, to peg , toPeg); //把n-1個(gè)圓盤從auxPeg借助fromPeg移至toPeg towers(n-1,auxPeg,toPeg,fromPeg); ,22,測(cè)試主函數(shù)如下： #include void main(void) Tow

10、ers(4, A, C, B); 程序運(yùn)行的輸出信息如下：,23,Move Disk 1 from Peg A to Peg B Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 3 from Peg A to Peg B Move Disk 1 from Peg C to Peg A Move Disk 2 from Peg C to Peg B Move Disk 1 from Peg A to Peg B Move Disk 4 from Peg A to Peg C Move Disk 1

11、 from Peg B to Peg C Move Disk 2 from Peg B to Peg A Move Disk 1 from Peg C to Peg A Move Disk 3 from Peg B to Peg C Move Disk 1 from Peg A to Peg B Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C,24,總結(jié)如下：遞歸算法的執(zhí)行過(guò)程是不斷地自調(diào)用，直到到達(dá)遞歸出口才結(jié)束自調(diào)用過(guò)程；到達(dá)遞歸出口后，遞歸算法開始按最后調(diào)用的過(guò)程最先返回的次序返回；返回到最外層的調(diào)用語(yǔ)句時(shí)遞

12、歸算法執(zhí)行過(guò)程結(jié)束。,25,6.4遞歸過(guò)程和運(yùn)行時(shí)棧,,對(duì)于非遞歸函數(shù)，調(diào)用函數(shù)在調(diào)用被調(diào)用函數(shù)前，系統(tǒng)要保存以下兩類信息： （1）調(diào)用函數(shù)的返回地址； （2）調(diào)用函數(shù)的局部變量值。 當(dāng)執(zhí)行完被調(diào)用函數(shù)，返回調(diào)用函數(shù)前，系統(tǒng)首先要恢復(fù)調(diào)用函數(shù)的局部變量值，然后返回調(diào)用函數(shù)的返回地址。,26,遞歸函數(shù)被調(diào)用時(shí)，系統(tǒng)要作的工作和非遞歸函數(shù)被調(diào)用時(shí)系統(tǒng)要作的工作在形式上類同，但保存信息的方法不同。 遞歸函數(shù)被調(diào)用時(shí)，系統(tǒng)需要一個(gè)運(yùn)行時(shí)棧.系統(tǒng)的運(yùn)行時(shí)棧也要保存上述兩類信息。每一層遞歸調(diào)用所需保存的信息構(gòu)成運(yùn)行時(shí)棧的一個(gè)工作記錄，在每進(jìn)入下一層遞歸調(diào)用時(shí)，系統(tǒng)就建立一個(gè)新的工作記錄，并把這個(gè)工作記錄進(jìn)

13、棧成為運(yùn)行時(shí)棧新的棧頂；每返回一層遞歸調(diào)用，就退棧一個(gè)工作記錄。因?yàn)闂ｍ數(shù)墓ぷ饔涗洷囟ㄊ钱?dāng)前正在運(yùn)行的遞歸函數(shù)的工作記錄，所以棧頂?shù)墓ぷ饔涗浺卜Q為活動(dòng)記錄。,27,6.5遞歸算法的效率分析,斐波那契數(shù)列Fib(n)的遞推定義是：,求第n項(xiàng)斐波那契數(shù)列的遞歸函數(shù)如下：,long Fib(int n) if(n == 0 || n == 1) return n; //遞歸出口 else return Fib(n-1) + Fib(n-2); //遞歸調(diào)用 ,,28,用歸納法可以證明求Fib(n)的遞歸調(diào)用次數(shù)等于2n-1；計(jì)算斐波那契數(shù)列的遞歸函數(shù)Fib(n)的時(shí)間復(fù)雜度為O

14、(2n)。計(jì)算斐波那契數(shù)列Fib(n)問(wèn)題，我們也可根據(jù)公式寫出循環(huán)方式求解的函數(shù)如下：,圖6-6 Fib(5)的遞歸調(diào)用樹,29,long Fib2(int n) long int oneBack, twoBack, current; int i; if(n == 0 || n == 1) return n; else oneBack = 1; twoBack = 0; for(i = 2; i <= n; i++) current = oneBack + twoBack; twoBack = oneBack; oneBack = current;

15、 return current; ,30,上述循環(huán)方式的計(jì)算斐波那契數(shù)列的函數(shù)Fib2(n)的時(shí)間復(fù)雜度為O(n)。對(duì)比循環(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ú)法保存，下一次要用到時(shí)還需要重新遞歸計(jì)算，因此其時(shí)間復(fù)雜度為O(2n) 。,31,*6.6遞歸

16、算法到非遞歸算法的轉(zhuǎn)換,有些問(wèn)題需要用低級(jí)程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)，而低級(jí)程序設(shè)計(jì)語(yǔ)言（如匯編語(yǔ)言）一般不支持遞歸，此時(shí)需要采用問(wèn)題的非遞歸結(jié)構(gòu)算法。一般來(lái)說(shuō)，存在如下兩種情況的遞歸算法。 （1）存在不借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，如階乘計(jì)算問(wèn)題、斐波那契數(shù)列的計(jì)算問(wèn)題、折半查找問(wèn)題等。這種情況，可以直接選用循環(huán)結(jié)構(gòu)的算法。,32,（2）存在借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，所有遞歸算法都可以借助堆棧轉(zhuǎn)換成循環(huán)結(jié)構(gòu)的非遞歸算法，如下邊例6-4設(shè)計(jì)的漢諾塔問(wèn)題的借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法。此時(shí)可以把遞歸算法轉(zhuǎn)換成相應(yīng)的非遞歸算法，有兩種轉(zhuǎn)換方法：一種方法是借助堆棧，用非遞歸算法形式化模擬遞歸算法的

17、執(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)相吻合。下面討論的例6-4是第二種情況下的第一種轉(zhuǎn)換方法的例子,33,6.7設(shè)計(jì)舉例,6.7.1 一般遞歸算法設(shè)計(jì)舉例,例6-5 設(shè)計(jì)一個(gè)輸出如下形式數(shù)值的遞歸算法。 n n n ... n ...... 3 3 3 2 2 1,34,問(wèn)題分析：該問(wèn)題可以看成由兩部分組成：一部分是輸出一行值為n的數(shù)值；另一部分是原問(wèn)題的子問(wèn)題，其參數(shù)為n-1。當(dāng)參數(shù)減到0時(shí)不再輸出任何數(shù)據(jù)值，因此遞歸的出口是當(dāng)參數(shù)n0時(shí)空語(yǔ)句返回。,算法設(shè)計(jì)：遞歸算法設(shè)計(jì)如下：

18、 void Display(int n) int i; for(i = 1; i 0) Display(n - 1);//遞歸 //n<=0為遞歸出口，遞歸出口為空語(yǔ)句 ,35,例6-6 設(shè)計(jì)求解委員會(huì)問(wèn)題的算法。委員會(huì)問(wèn)題是：從一個(gè)有n個(gè)人的團(tuán)體中抽出k (kn)個(gè)人組成一個(gè)委員會(huì)，計(jì)算共有多少種構(gòu)成方法。 問(wèn)題分析：從n個(gè)人中抽出k(kn)個(gè)人的問(wèn)題是一個(gè)組合問(wèn)題。把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ì)于第二部分，則

19、問(wèn)題簡(jiǎn)化為從n-1個(gè)人中抽出k個(gè)人的問(wèn)題。圖6-7給出了n=5, k=2時(shí)問(wèn)題的分解示意圖。,36,圖6-7 委員會(huì)問(wèn)題分解示意圖,37,當(dāng)n=k或k=0時(shí)，該問(wèn)題可直接求解，數(shù)值均為1，這是算法的遞歸出口。因此，委員會(huì)問(wèn)題的遞推定義式為：,38,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); ,39,例6-7 求兩個(gè)正整數(shù)n和m最大公約數(shù)的遞推定義式為：,要求： （1）編寫求解該問(wèn)題

20、的遞歸算法； （2）分析當(dāng)調(diào)用語(yǔ)句為Gcd(30, 4)時(shí)算法的執(zhí)行過(guò)程和執(zhí)行結(jié)果； （3）分析當(dāng)調(diào)用語(yǔ)句為Gcd(97, 5)時(shí)算法的執(zhí)行過(guò)程和執(zhí)行結(jié)果； （4）編寫求解該問(wèn)題的循環(huán)結(jié)構(gòu)算法。,40,解：（1）遞歸算法如下： int Gcd(int n, int m) if(n n) return Gcd(m, n); else return Gcd(m, n % m); ,41,（2）調(diào)用語(yǔ)句為Gcd(30, 4)時(shí)，因mn，遞歸調(diào)用Gcd(97, 5)；因m