遞歸算法課件2

第6章遞歸算法第6章遞歸算法2main()……fn=Fact(3)……Fact(3)……y=Fact(2)……return3*yFact(2)……y=Fact(1)……return2*y遞歸調(diào)用的執(zhí)行過程：Fact(1)……y=Fact(0)……return1*yFact(0)…………return12main()Fact(3)Fact(2)遞歸調(diào)用的執(zhí)行36.4遞歸過程和運(yùn)行時(shí)棧

對于非遞歸函數(shù)，調(diào)用函數(shù)在調(diào)用被調(diào)用函數(shù)前，系統(tǒng)要保存以下兩類信息：（1）調(diào)用函數(shù)的返回地址（從而能執(zhí)行下一語句）；（2）調(diào)用函數(shù)的局部變量值。當(dāng)執(zhí)行完被調(diào)用函數(shù)，返回調(diào)用函數(shù)前，系統(tǒng)首先要恢復(fù)調(diào)用函數(shù)的局部變量值，然后返回調(diào)用函數(shù)的返回地址。遞歸函數(shù)被調(diào)用時(shí)，系統(tǒng)要做的工作和非遞歸函數(shù)被調(diào)用時(shí)系統(tǒng)要作的工作在形式上類同，但保存信息的內(nèi)容和方法不同。36.4遞歸過程和運(yùn)行時(shí)棧對于非遞歸函數(shù)，調(diào)用函數(shù)在4保存內(nèi)容：每一層遞歸調(diào)用所需要保存的信息構(gòu)成一個(gè)工作記錄，通常包括如下內(nèi)容：

（1）本次遞歸調(diào)用中的局部變量值；

（2）返回地址，即本次遞歸過程調(diào)用語句的后繼語句的地址；

（3）本次調(diào)用中與形參結(jié)合的實(shí)參值，包括函數(shù)名、引用參數(shù)與數(shù)值參數(shù)等。工作記錄局部變量返回地址參數(shù)4保存內(nèi)容：工作記錄局部變量返回地址參5我們以計(jì)算階乘的遞歸函數(shù)為例，說明遞歸函數(shù)調(diào)用時(shí)運(yùn)行時(shí)棧中工作記錄的變化過程。longFact(intn){intx;longy;Ifn==0return1;else{x=n-1;y=Fact(x);returnn*y;}}5我們以計(jì)算階乘的遞歸函數(shù)為例，說明遞歸函數(shù)調(diào)用時(shí)運(yùn)行時(shí)棧中6

由于函數(shù)的地址是系統(tǒng)動態(tài)分配的，調(diào)用函數(shù)的返回地址因此也是動態(tài)變化的，不好給出具體數(shù)值，故下圖中沒有給出調(diào)用函數(shù)的返回地址。

棧頂321棧底0nxyFact初始時(shí)運(yùn)行時(shí)棧的變化過程

棧頂321棧底03***nxyFact調(diào)用Fact(3)

棧頂3212***棧底032**nxyFact調(diào)用Fact(2)

棧頂321***121**棧底032**nxyFact調(diào)用Fact(1)

棧頂30**1210121**棧底032**nxyFact調(diào)用Fact(0)

棧頂321011121**棧底032**nxyFact返回Fact(0)

棧頂3212112棧底032**nxyFact返回Fact(1)

棧頂321棧底03226nxyFact返回Fact(2)

棧頂321棧底0nxyFact返回Fact(3)longFact(intn){intx;longy;Ifn==0return1;else{x=n-1;y=Fact(x);returnn*y;}}6由于函數(shù)的地址是系統(tǒng)動態(tài)分配的，調(diào)用函數(shù)的返76.6遞歸算法到非遞歸算法的轉(zhuǎn)換

有些問題需要用低級程序設(shè)計(jì)語言來實(shí)現(xiàn)，而低級程序設(shè)計(jì)語言（如匯編語言）一般不支持遞歸，此時(shí)需要采用問題的非遞歸結(jié)構(gòu)算法。一般來說，存在如下兩種情況的遞歸算法。（1）存在不借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，如階乘計(jì)算問題、斐波那契數(shù)列的計(jì)算問題、折半查找問題等。（2）存在借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，所有遞歸算法都可以借助堆棧轉(zhuǎn)換成循環(huán)結(jié)構(gòu)的非遞歸算法，如漢諾塔問題可以借助堆棧的循環(huán)結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法。76.6遞歸算法到非遞歸算法的轉(zhuǎn)換有些問題需要用低級程序8

對于第一種情況，可以直接選用循環(huán)結(jié)構(gòu)的算法。對于第二種情況，可以把遞歸算法轉(zhuǎn)換成相應(yīng)的非遞歸算法，此時(shí)有兩種轉(zhuǎn)換方法：一種方法是借助堆棧，用非遞歸算法形式化模擬遞歸算法的執(zhí)行過程；另一種方法是根據(jù)要求解問題的特點(diǎn)，設(shè)計(jì)借助堆棧的循環(huán)結(jié)構(gòu)算法。這兩種方法都需要使用堆棧，這是因?yàn)槎褩５暮筮M(jìn)先出特點(diǎn)正好和遞歸函數(shù)的運(yùn)行特點(diǎn)相吻合。通常，一個(gè)遞歸算法的模擬算法的復(fù)雜度與其本身的復(fù)雜度一樣。8對于第一種情況，可以直接選用循環(huán)結(jié)構(gòu)的算法。96.7設(shè)計(jì)舉例6.7.1一般遞歸算法設(shè)計(jì)舉例

例6-5設(shè)計(jì)一個(gè)輸出如下形式數(shù)值的遞歸算法。

nnn...n ...... 333 22 196.7設(shè)計(jì)舉例6.7.1一般遞歸算法設(shè)計(jì)舉例例6-510問題分析：該問題可以看成由兩部分組成：一部分是輸出一行值為n的數(shù)值；另一部分是原問題的子問題，其參數(shù)為n-1。當(dāng)參數(shù)減到0時(shí)不再輸出任何數(shù)據(jù)值，因此遞歸的出口是當(dāng)參數(shù)n≤0時(shí)空語句返回。

voidDisplay(intn){inti;

for(i=1;i<=n;i++) printf(“%3d”,n); printf(“\n”);

if(n>0)Display(n-1); //遞歸

//n<=0為遞歸出口，遞歸出口為空語句

}10問題分析：該問題可以看成由兩部分組成：一部分是輸出一行值11例6-6設(shè)計(jì)求解委員會問題的算法。委員會問題是：從一個(gè)有n個(gè)人的團(tuán)體中抽出k(k≤n)個(gè)人組成一個(gè)委員會，計(jì)算共有多少種構(gòu)成方法。問題分析：從n個(gè)人中抽出k(k≤n)個(gè)人的問題是一個(gè)組合問題。即求組合數(shù)公式C(n,k)。由于要所用遞歸算法,大家容易想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k),11例6-6設(shè)計(jì)求解委員會問題的算法。委員會問題是：從一個(gè)

這個(gè)公式大家可以這樣理解:把n個(gè)人固定位置后，從n個(gè)人中抽出k個(gè)人的問題可分解為兩部分之和：第一部分是第一個(gè)人包括在k個(gè)人中，第二部分是第一個(gè)人不包括在k個(gè)人中。

對于第一部分，則問題簡化為從n-1個(gè)人中抽出k-1個(gè)人的問題；對于第二部分，則問題簡化為從n-1個(gè)人中抽出k個(gè)人的問題。這個(gè)公式大家可以這樣理解:把n個(gè)人固定位置后13

當(dāng)n=k或k=0時(shí)，該問題可直接求解，數(shù)值均為1，這是算法的遞歸出口。因此，委員會問題的遞推定義式為：intComm(intn,intk){if(n<1||k<0||k>n)return0;

if(k==0)return1; if(n==k)return1; returnComm(n-1,k-1)+Comm(n-1,k);}13當(dāng)n=k或k=0時(shí)，該問題可直接求解，數(shù)值均為1第6章遞歸算法課件215例6-7求兩個(gè)正整數(shù)n和m最大公約數(shù)的遞推定義式為：要求：（1）編寫求解該問題的遞歸算法；（2）分析當(dāng)調(diào)用語句為Gcd(30,4)時(shí)算法的執(zhí)行過程和執(zhí)行結(jié)果；（3）分析當(dāng)調(diào)用語句為Gcd(5,97)時(shí)算法的執(zhí)行過程和執(zhí)行結(jié)果；（4）編寫求解該問題的循環(huán)結(jié)構(gòu)算法。15例6-7求兩個(gè)正整數(shù)n和m最大公約數(shù)的遞推定義式為：16解：（1）遞歸算法如下：

intGcd(intn,intm){if(n<0||m<0)exit(0);if(m==0)returnn;elseif(m>n)returnGcd(m,n);elsereturnGcd(m,n%m);}16解：（1）遞歸算法如下：17（2）調(diào)用語句為Gcd(30,4)時(shí)，因m<n，遞歸調(diào)用Gcd(4,2)；因m<n，遞歸調(diào)用Gcd(2,0)；因m=0，到達(dá)遞歸出口，函數(shù)最終返回值為n=2，即30和4的最大公約數(shù)為2（3）調(diào)用語句為Gcd(5,97)時(shí)，因m>n，遞歸調(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。17（2）調(diào)用語句為Gcd(30,4)時(shí)，因m<n，遞歸調(diào)18（4）循環(huán)結(jié)構(gòu)算法intGcd2(intn,intm){inttn,tm,temp;if(n<0||m<0)return-1;if(m>n){tn=m;tm=n;} else{tn=n;tm=m;}

Whiletm!=0{temp=tn;tn=tm;tm=temp%tm;}returntn;}18（4）循環(huán)結(jié)構(gòu)算法196.7.2回溯法及其設(shè)計(jì)舉例

回溯法是遞歸算法的一種特殊形式，回溯法的基本思想是：對一個(gè)包括有很多結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有若干個(gè)搜索分支的問題，把原問題分解為對若干個(gè)子問題求解的算法。當(dāng)搜索到某個(gè)結(jié)點(diǎn)、發(fā)現(xiàn)無法再繼續(xù)搜索下去時(shí)，就讓搜索過程回溯退到該結(jié)點(diǎn)的前一結(jié)點(diǎn)，繼續(xù)搜索這個(gè)結(jié)點(diǎn)的其他尚未搜索過的分支；如果發(fā)現(xiàn)這個(gè)結(jié)點(diǎn)也無法再繼續(xù)搜索下去時(shí)，就讓搜索過程回溯（即退回）到這個(gè)結(jié)點(diǎn)的前一結(jié)點(diǎn)繼續(xù)這樣的搜索過程；這樣的搜索過程一直進(jìn)行到搜索到問題的解或搜索完了全部可搜索分支沒有解存在為止。196.7.2回溯法及其設(shè)計(jì)舉例回溯法是遞歸算法20

例6-10設(shè)計(jì)求解迷宮問題的算法并用實(shí)際例子測試。20例6-10設(shè)計(jì)求解迷宮問題的算法并用實(shí)際例子測第6章遞歸算法課件2算法如下：22結(jié)構(gòu)體如下：Typedefstruct{ intleft; intforward; intright;}InterSection;Typedefstruct{ intmazeSize;interSection*intSec;intExit;}算法如下：22結(jié)構(gòu)體如下：TypedefstructTyp6020356004000000700723623第6章遞歸算法第6章遞歸算法25main()……fn=Fact(3)……Fact(3)……y=Fact(2)……return3*yFact(2)……y=Fact(1)……return2*y遞歸調(diào)用的執(zhí)行過程：Fact(1)……y=Fact(0)……return1*yFact(0)…………return12main()Fact(3)Fact(2)遞歸調(diào)用的執(zhí)行266.4遞歸過程和運(yùn)行時(shí)棧

對于非遞歸函數(shù)，調(diào)用函數(shù)在調(diào)用被調(diào)用函數(shù)前，系統(tǒng)要保存以下兩類信息：（1）調(diào)用函數(shù)的返回地址（從而能執(zhí)行下一語句）；（2）調(diào)用函數(shù)的局部變量值。當(dāng)執(zhí)行完被調(diào)用函數(shù)，返回調(diào)用函數(shù)前，系統(tǒng)首先要恢復(fù)調(diào)用函數(shù)的局部變量值，然后返回調(diào)用函數(shù)的返回地址。遞歸函數(shù)被調(diào)用時(shí)，系統(tǒng)要做的工作和非遞歸函數(shù)被調(diào)用時(shí)系統(tǒng)要作的工作在形式上類同，但保存信息的內(nèi)容和方法不同。36.4遞歸過程和運(yùn)行時(shí)棧對于非遞歸函數(shù)，調(diào)用函數(shù)在27保存內(nèi)容：每一層遞歸調(diào)用所需要保存的信息構(gòu)成一個(gè)工作記錄，通常包括如下內(nèi)容：

（1）本次遞歸調(diào)用中的局部變量值；

（2）返回地址，即本次遞歸過程調(diào)用語句的后繼語句的地址；

（3）本次調(diào)用中與形參結(jié)合的實(shí)參值，包括函數(shù)名、引用參數(shù)與數(shù)值參數(shù)等。工作記錄局部變量返回地址參數(shù)4保存內(nèi)容：工作記錄局部變量返回地址參28我們以計(jì)算階乘的遞歸函數(shù)為例，說明遞歸函數(shù)調(diào)用時(shí)運(yùn)行時(shí)棧中工作記錄的變化過程。longFact(intn){intx;longy;Ifn==0return1;else{x=n-1;y=Fact(x);returnn*y;}}5我們以計(jì)算階乘的遞歸函數(shù)為例，說明遞歸函數(shù)調(diào)用時(shí)運(yùn)行時(shí)棧中29

由于函數(shù)的地址是系統(tǒng)動態(tài)分配的，調(diào)用函數(shù)的返回地址因此也是動態(tài)變化的，不好給出具體數(shù)值，故下圖中沒有給出調(diào)用函數(shù)的返回地址。

棧頂321棧底0nxyFact初始時(shí)運(yùn)行時(shí)棧的變化過程

棧頂321棧底03***nxyFact調(diào)用Fact(3)

棧頂3212***棧底032**nxyFact調(diào)用Fact(2)

棧頂321***121**棧底032**nxyFact調(diào)用Fact(1)

棧頂30**1210121**棧底032**nxyFact調(diào)用Fact(0)

棧頂321011121**棧底032**nxyFact返回Fact(0)

棧頂3212112棧底032**nxyFact返回Fact(1)

棧頂321棧底03226nxyFact返回Fact(2)

棧頂321棧底0nxyFact返回Fact(3)longFact(intn){intx;longy;Ifn==0return1;else{x=n-1;y=Fact(x);returnn*y;}}6由于函數(shù)的地址是系統(tǒng)動態(tài)分配的，調(diào)用函數(shù)的返306.6遞歸算法到非遞歸算法的轉(zhuǎn)換

有些問題需要用低級程序設(shè)計(jì)語言來實(shí)現(xiàn)，而低級程序設(shè)計(jì)語言（如匯編語言）一般不支持遞歸，此時(shí)需要采用問題的非遞歸結(jié)構(gòu)算法。一般來說，存在如下兩種情況的遞歸算法。（1）存在不借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，如階乘計(jì)算問題、斐波那契數(shù)列的計(jì)算問題、折半查找問題等。（2）存在借助堆棧的循環(huán)結(jié)構(gòu)的非遞歸算法，所有遞歸算法都可以借助堆棧轉(zhuǎn)換成循環(huán)結(jié)構(gòu)的非遞歸算法，如漢諾塔問題可以借助堆棧的循環(huán)結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法。76.6遞歸算法到非遞歸算法的轉(zhuǎn)換有些問題需要用低級程序31

對于第一種情況，可以直接選用循環(huán)結(jié)構(gòu)的算法。對于第二種情況，可以把遞歸算法轉(zhuǎn)換成相應(yīng)的非遞歸算法，此時(shí)有兩種轉(zhuǎn)換方法：一種方法是借助堆棧，用非遞歸算法形式化模擬遞歸算法的執(zhí)行過程；另一種方法是根據(jù)要求解問題的特點(diǎn)，設(shè)計(jì)借助堆棧的循環(huán)結(jié)構(gòu)算法。這兩種方法都需要使用堆棧，這是因?yàn)槎褩５暮筮M(jìn)先出特點(diǎn)正好和遞歸函數(shù)的運(yùn)行特點(diǎn)相吻合。通常，一個(gè)遞歸算法的模擬算法的復(fù)雜度與其本身的復(fù)雜度一樣。8對于第一種情況，可以直接選用循環(huán)結(jié)構(gòu)的算法。326.7設(shè)計(jì)舉例6.7.1一般遞歸算法設(shè)計(jì)舉例

例6-5設(shè)計(jì)一個(gè)輸出如下形式數(shù)值的遞歸算法。

nnn...n ...... 333 22 196.7設(shè)計(jì)舉例6.7.1一般遞歸算法設(shè)計(jì)舉例例6-533問題分析：該問題可以看成由兩部分組成：一部分是輸出一行值為n的數(shù)值；另一部分是原問題的子問題，其參數(shù)為n-1。當(dāng)參數(shù)減到0時(shí)不再輸出任何數(shù)據(jù)值，因此遞歸的出口是當(dāng)參數(shù)n≤0時(shí)空語句返回。

voidDisplay(intn){inti;

for(i=1;i<=n;i++) printf(“%3d”,n); printf(“\n”);

if(n>0)Display(n-1); //遞歸

//n<=0為遞歸出口，遞歸出口為空語句

}10問題分析：該問題可以看成由兩部分組成：一部分是輸出一行值34例6-6設(shè)計(jì)求解委員會問題的算法。委員會問題是：從一個(gè)有n個(gè)人的團(tuán)體中抽出k(k≤n)個(gè)人組成一個(gè)委員會，計(jì)算共有多少種構(gòu)成方法。問題分析：從n個(gè)人中抽出k(k≤n)個(gè)人的問題是一個(gè)組合問題。即求組合數(shù)公式C(n,k)。由于要所用遞歸算法,大家容易想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k),11例6-6設(shè)計(jì)求解委員會問題的算法。委員會問題是：從一個(gè)

這個(gè)公式大家可以這樣理解:把n個(gè)人固定位置后，從n個(gè)人中抽出k個(gè)人的問題可分解為兩部分之和：第一部分是第一個(gè)人包括在k個(gè)人中，第二部分是第一個(gè)人不包括在k個(gè)人中。

對于第一部分，則問題簡化為從n-1個(gè)人中抽出k-1個(gè)人的問題；對于第二部分，則問題簡化為從n-1個(gè)人中抽出k個(gè)人的問題。這個(gè)公式大家可以這樣理解:把n個(gè)人固定位置后36

當(dāng)n=k或k=0時(shí)，該問題可直接求解，數(shù)值均為1，這是算法的遞歸出口。因此，委員會問題的遞推定義式為：intComm(intn,intk){if(n<1||k<0||k>n)return0;

if(k==0)return1; if(n==k)return1; returnComm(n-1,k-1)+Comm(n-1,k);}13當(dāng)n=k或k=0時(shí)，該問題可直接求解，數(shù)值均為1第6章遞歸算法課件238例6-7求兩個(gè)正整數(shù)n和m最大公約數(shù)的遞推定義式為：要求：（1）編寫求解該問題的遞歸算法；（2）分析當(dāng)調(diào)用語句為Gcd(30,4)時(shí)算法的執(zhí)行過程和執(zhí)行結(jié)果；（3）分析當(dāng)調(diào)用語句為Gcd(5,97)時(shí)算法的執(zhí)行過程和執(zhí)行結(jié)果；（4）編寫求解該問題的循環(huán)結(jié)構(gòu)算法。15例6-7求兩個(gè)正整數(shù)n和m最大公約數(shù)的遞推定義式為：39解：（1）遞歸算法如下：

intGcd(intn,intm){if(n<0||m<0)exit(0);if(m==0)returnn;elseif(m>n)returnGcd(m,n);elsereturnGcd(m,n%m);}16解：（1）遞歸算法如下：40（2）調(diào)用語句為Gcd(30,4)時(shí)，因m<n，遞歸調(diào)用Gcd(4,2)；因m<n，遞歸調(diào)用Gcd(2,0)；因m=0，到達(dá)遞歸出口，函數(shù)最終返回值為n=2，即30和4的最大公約數(shù)為2（3）調(diào)用語句為Gcd(5,97)時(shí)，因m>n，遞歸調(diào)用Gcd(97,5)；因m<n，遞歸調(diào)用Gcd(5,2)；因m<n，遞歸調(diào)用G