《算法與結(jié)構(gòu)課件第二章遞歸(華北電力大學(xué)科技學(xué)院).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法與結(jié)構(gòu)課件第二章遞歸(華北電力大學(xué)科技學(xué)院).ppt（58頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

計(jì)算機(jī)算法設(shè)計(jì)與分析,NorthChinaElectricPowerUniversity,ComputerAlgorithmsDesignreturnn*Factorial(n-1);},2遞歸算法的應(yīng)用和實(shí)現(xiàn),如果問題的數(shù)據(jù)結(jié)構(gòu)是遞歸的，問題的定義是遞歸的，問題的解法是遞歸的，可以考慮用遞歸算法。,看下面的數(shù)據(jù)結(jié)構(gòu)：,,,,,Head,^,…,,,,Head,,,這是單鏈表，每個(gè)結(jié)點(diǎn)有兩個(gè)域：數(shù)據(jù)域和指針域。它是一種遞歸的結(jié)構(gòu)，可定義為：1)一個(gè)結(jié)點(diǎn)，其指針域?yàn)閚ull，是一個(gè)單鏈表；2)一個(gè)結(jié)點(diǎn)，其指針域?yàn)橛行е羔樦赶蛞粋€(gè)單鏈表，仍是一個(gè)單鏈表。,1)問題的數(shù)據(jù)結(jié)構(gòu)是遞歸的,NorthChinaElectricPowerUniversity,若存在如上定義的一個(gè)單鏈表，現(xiàn)要實(shí)現(xiàn)打印最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的值，可用下面遞歸過程：,templateclasslink_list{Typedata;link_list*next;};templatevoidsearch1(link_list*h){if(h->next==null)coutdata;elsesearch1(h->next);},NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,二叉樹(BinaryTree)也是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，其遞歸定義為：1)它是一棵空樹；2)它是由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左右子樹的二叉樹構(gòu)成。,要遍歷一棵二叉樹可以采用下面的遞歸算法：,voidTraverse(Bitptr*t){if(t!=null){coutdata;Traverse(t->lchild);Traverse(t->rchild);}},NorthChinaElectricPowerUniversity,例：Fibonacci數(shù)列無窮數(shù)列1,1,2,3,5,8,13,21,34,55,…,稱為Fibonacci數(shù)列。它可以遞歸地定義為：,Fib(n)=,,1n=0,1n=1,Fib(n-1)+Fib(n-2)n>1,第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：intFibonacci(intn){if(nm>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤m-1的劃分組成。以上的關(guān)系實(shí)際上給出了計(jì)算q(n,m)的遞歸式如下：,q(n,m)=,,1m=1,q(n,n)nm>1,0n<1或m<1,遞歸算法的設(shè)計(jì)方法,,遞歸算法既是一種有效的算法設(shè)計(jì)方法，也是一種有效的分析問題的方法。遞歸算法求解問題的基本思想是：對(duì)于一個(gè)較為復(fù)雜的問題，把原問題分解成若干個(gè)相對(duì)簡單且類同的子問題,這樣，原問題就可遞推得到解。適宜于用遞歸算法求解的問題的充分必要條件是：（1）問題具有某種可借用的類同自身的子問題描述的性質(zhì)；（2）某一有限步的子問題（也稱作本原問題）有直接的解存在。當(dāng)一個(gè)問題存在上述兩個(gè)基本要素時(shí)，該問題的遞歸算法的設(shè)計(jì)方法是：（1）把對(duì)原問題的求解設(shè)計(jì)成包含有對(duì)子問題求解的形式。（2）設(shè)計(jì)遞歸出口。,,例設(shè)計(jì)模擬漢諾塔問題求解過程的算法。漢諾塔問題的描述是：設(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)過程中大盤子不能放在小盤子上面；（3）在移動(dòng)過程中盤子可以放在A，B，C的任意一個(gè)柱子上。,問題分析：可以用遞歸方法求解n個(gè)盤子的漢諾塔問題。,,基本思想：1個(gè)盤子的漢諾塔問題可直接移動(dòng)。n個(gè)盤子的漢諾塔問題可遞歸表示為，首先把上邊的n-1個(gè)盤子從A柱移到B柱，然后把最下邊的一個(gè)盤子從A柱移到C柱，最后把移到B柱的n-1個(gè)盤子再移到C柱。4個(gè)盤子漢諾塔問題的遞歸求解示意圖如圖6-4所示。,,圖6-4漢諾塔問題的遞歸求解示意圖,,,,,,,,,,,,,,,,,,,,,,,,,,Y,X,Z,以三個(gè)盤為例：,A,B,C,,算法設(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；最后，漢諾塔問題的求解是一個(gè)處理過程，因此算法的輸出是n個(gè)盤子從柱子fromPeg借助柱子auxPeg移動(dòng)到柱子toPeg的移動(dòng)步驟，我們?cè)O(shè)計(jì)每一步的移動(dòng)為屏幕顯示如下形式的信息：MoveDiskifromPegXtoPegY這樣，漢諾塔問題的遞歸算法可設(shè)計(jì)如下：,voidtowers(intn,charfromPeg,chartoPeg,charauxPeg){if(n==1)//遞歸出口{printf("%s%c%s%c\n","movedisk1frompeg",fromPeg,"topeg",toPeg);return;}//把n-1個(gè)圓盤從fromPeg借助toPeg移至auxPegtowers(n-1,fromPeg,auxPeg,toPeg);//把圓盤n由fromPeg直接移至toPegprintf("%s%d%s%c%s%c\n","movedisk",n,"frompeg",fromPeg,"topeg",toPeg);//把n-1個(gè)圓盤從auxPeg借助fromPeg移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);},測試主函數(shù)如下：#includevoidmain(void){Towers(4,A,C,B);}程序運(yùn)行的輸出信息如下：,MoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk3fromPegAtoPegBMoveDisk1fromPegCtoPegAMoveDisk2fromPegCtoPegBMoveDisk1fromPegAtoPegBMoveDisk4fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk2fromPegBtoPegAMoveDisk1fromPegCtoPegAMoveDisk3fromPegBtoPegCMoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegC,總結(jié)如下：遞歸算法的執(zhí)行過程是不斷地自調(diào)用，直到到達(dá)遞歸出口才結(jié)束自調(diào)用過程；到達(dá)遞歸出口后，遞歸算法開始按最后調(diào)用的過程最先返回的次序返回；返回到最外層的調(diào)用語句時(shí)遞歸算法執(zhí)行過程結(jié)束。,代碼,,遞歸過程的實(shí)現(xiàn),,對(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ù)的返回地址。遞歸函數(shù)被調(diào)用時(shí)，系統(tǒng)要作的工作和非遞歸函數(shù)被調(diào)用時(shí)系統(tǒng)要作的工作在形式上類同，但保存信息的方法不同。,遞歸函數(shù)被調(diào)用時(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)棧成為運(yùn)行時(shí)棧新的棧頂；每返回一層遞歸調(diào)用，就退棧一個(gè)工作記錄。因?yàn)闂ｍ數(shù)墓ぷ饔涗洷囟ㄊ钱?dāng)前正在運(yùn)行的遞歸函數(shù)的工作記錄，所以棧頂?shù)墓ぷ饔涗浺卜Q為活動(dòng)記錄。,設(shè)計(jì)舉例,一般遞歸算法設(shè)計(jì)舉例,例1設(shè)計(jì)一個(gè)輸出如下形式數(shù)值的遞歸算法。nnn...n......333221,問題分析：該問題可以看成由兩部分組成：一部分是輸出一行值為n的數(shù)值；另一部分是原問題的子問題，其參數(shù)為n-1。當(dāng)參數(shù)減到0時(shí)不再輸出任何數(shù)據(jù)值，因此遞歸的出口是當(dāng)參數(shù)n≤0時(shí)空語句返回。算法設(shè)計(jì)：遞歸算法設(shè)計(jì)如下：voidDisplay(intn){inti;for(i=1;i0)Display(n-1);//遞歸//n<=0為遞歸出口，遞歸出口為空語句},代碼,例6-6設(shè)計(jì)求解委員會(huì)問題的算法。委員會(huì)問題是：從一個(gè)有n個(gè)人的團(tuán)體中抽出k(k≤n)個(gè)人組成一個(gè)委員會(huì)，計(jì)算共有多少種構(gòu)成方法。問題分析：從n個(gè)人中抽出k(k≤n)個(gè)人的問題是一個(gè)組合問題。把n個(gè)人固定位置后，從n個(gè)人中抽出k個(gè)人的問題可分解為兩部分之和：第一部分是第一個(gè)人包括在k個(gè)人中，第二部分是第一個(gè)人不包括在k個(gè)人中。對(duì)于第一部分，則問題簡化為從n-1個(gè)人中抽出k-1個(gè)人的問題；對(duì)于第二部分，則問題簡化為從n-1個(gè)人中抽出k個(gè)人的問題。圖6-7給出了n=5,k=2時(shí)問題的分解示意圖。,圖6-7委員會(huì)問題分解示意圖,當(dāng)n=k或k=0時(shí)，該問題可直接求解，數(shù)值均為1，這是算法的遞歸出口。因此，委員會(huì)問題的遞推定義式為：,intComm(intn,intk){if(nn)return0;if(k==0)return1;if(n==k)return1;returnComm(n-1,k-1)+Comm(n-1,k);},例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(97,5)時(shí)算法的執(zhí)行過程和執(zhí)行結(jié)果；（4）編寫求解該問題的循環(huán)結(jié)構(gòu)算法。,,解：（1）遞歸算法如下：intGcd(intn,intm){if(nn)returnGcd(m,n);elsereturnGcd(m,n%m);}（2）調(diào)用語句為Gcd(30,4)時(shí)，因m1,0n<1或m1),NorthChinaElectricPowerUniversity,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(2),Fib(1),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),將遞歸算法轉(zhuǎn)化成非遞歸算法的方法：,1)設(shè)計(jì)迭代算法：如果一個(gè)函數(shù)既有遞歸形式的定義又有非遞歸的迭代形式的定義，則可以用循環(huán)結(jié)構(gòu)設(shè)計(jì)出迭代算法。一般說來，如果在一個(gè)函數(shù)或過程中只遞歸調(diào)用它一次，那么它的計(jì)算或執(zhí)行過程可以看成是線性變化的。,n!,,(n-1)!,,(n-2)!,,,,1!,,0!,,,從頂?shù)降走f歸,從底到頂返回,NorthChinaElectricPowerUniversity,intFact(intn){if(n==0)return1;elsereturnn*Fact(n-1);}intFact2(intn){x=1;for(i=1;i<=n;i++)x=i*x;returnx;},以Fibnaocci數(shù)列為例，看非遞歸算法的轉(zhuǎn)化,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(1),Fib(2),Fib(1),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),Fib(0),,,,,,,,,,,,,,,Fib(5),Fib(4),Fib(3),Fib(2),Fib(0),Fib(1),NorthChinaElectricPowerUniversity,,intFib2(intn){if(n<2)return(n);else{inty=0;intx=1;intz;for(inti=2;i<=n;i++){z=y;y=x;x=z+y;}return(x);}},2)消除尾遞歸：遞歸調(diào)用是最后一步操作,可以用循環(huán)結(jié)構(gòu)通過設(shè)置一些工作單元，把遞歸算法轉(zhuǎn)化為非遞歸算法。開始令工作單元等于外層的實(shí)際參數(shù)，以后隨著循環(huán)的執(zhí)行，不斷向里層變化，直到原遞歸調(diào)用的最里層的情況。循環(huán)結(jié)束后，執(zhí)行原屬于最里層的操作，而后整個(gè)算法結(jié)束。,NorthChinaElectricPowerUniversity,例:尋找單鏈表的最后一個(gè)結(jié)點(diǎn)并打印其數(shù)據(jù)域的值的過程search就是一個(gè)尾遞歸過程。,templateclasslink_list{Typedata;link_list*next;};voidsearch(h:link_list){if(h.next==null)cout<rchild)對(duì)應(yīng)）。其中，①與②的連接沒問題。但②與③如何連接需要考慮。為了做③，必須“知道”XR的“根指針”即結(jié)點(diǎn)X的右指針t->rchild:可是X的左子樹XL上沒有這個(gè)指針。因此，應(yīng)該在做②之前便將指針t->rchild保存起來;并當(dāng)任務(wù)②完成之后“取出”該指針以便執(zhí)行任務(wù)③。在這以后，指針t->rchild就沒有保存價(jià)值了。對(duì)于先根遍歷來說，完成了任務(wù)③也就完成了對(duì)以X為根的整個(gè)子樹的遍歷，可以直接退回到X的父結(jié)點(diǎn)。,NorthChinaElectricPowerUniversity,根據(jù)以上分析，先根遍歷的非遞歸算法需引入任務(wù)棧以保存每個(gè)結(jié)點(diǎn)的右指針。這樣，非遞歸算法在二叉鏈表的任一結(jié)點(diǎn)X上的主要操作步驟可歸納如下：,①訪問結(jié)點(diǎn)X；②結(jié)點(diǎn)X的右指針進(jìn)棧;③若XL不空，沿X的左指針遍歷XL；④從棧中取出X的右指針并將其退棧；⑤若XR不空，沿X右指針遍歷XR。,需要特別考慮的是，在二叉鏈表上，對(duì)任一結(jié)點(diǎn)X的任何操作都必須借助于指向它的指針的指引才能進(jìn)行，而這一指針存在于X的父結(jié)點(diǎn)的某個(gè)指針域中。唯一的例外是根結(jié)點(diǎn)，指向它的指針是根指針。為了統(tǒng)一處理這兩種情況，可在算法的初始化中先將指針進(jìn)棧，而在循環(huán)體的開頭做取棧頂操作。這樣，第一次從棧中取出的正是根指針；而以后棧中存儲(chǔ)（并取出）的是各個(gè)結(jié)點(diǎn)的右指針。,NorthChinaElectricPowerUniversity,綜合以上考慮，先根遍歷非遞歸算法的非形式描述如下：根指針進(jìn)棧；while(棧不空){s=棧頂元素；退棧；while(s!=NULL)/*根或左、右子樹不空時(shí)繼續(xù)遍歷*/{visit(s);s->rchild進(jìn)棧;/*保存右指針*/s=s->lchild;/*準(zhǔn)備遍歷左子樹*/}},NorthChinaElectricPowerUniversity,voidpreorder1(bitreptrt)/*先根遍歷根結(jié)點(diǎn)為t的二叉樹*/{bitreptrstack[stacksize];/*工作棧*/inttop;top=0;stack[top]=t;/*根指針進(jìn)棧*/while(top>=0){s=stack[top];/*讀棧頂元素到S中*/top--;/*退棧*/while(s!=NULL){visit(s);top++;stack[top]=s->rchild;/*右指針進(jìn)棧保存*/s=s->lchild;/*修改s以便繼續(xù)遍歷左子樹*/}}},通過上面的例子可以看出，工作棧在消除遞歸中的基本作用是提供一種控制機(jī)構(gòu)。在非遞歸算法執(zhí)行過程中的某些“關(guān)鍵”時(shí)刻，用棧頂元素來“引導(dǎo)”下一步操作的“走向”。為了達(dá)到這一目的，必須提前將這些有用的信息進(jìn)棧保存。在上面的例子中，工作棧保存的是各個(gè)結(jié)點(diǎn)的右指針，這些指針也就是二叉樹上各結(jié)點(diǎn)的右子樹的根指針。顯然，這些根指針正是先根遍歷遞歸算法中包含的一些遞歸調(diào)用的實(shí)參；這些實(shí)參在非遞歸算法中若不及時(shí)保存就會(huì)丟失。因此，遞歸算法中的調(diào)用一返回控制被工作棧的作用所取代，從而將遞歸算法轉(zhuǎn)換成非遞歸算法。,NorthChinaElectricPowerUniversity,2.n!的非遞歸實(shí)現(xiàn),首先設(shè)定一個(gè)工作記錄棧S,其類型定義如下：#definemaxsize100structsqlStack{intElem[maxsize];inttop;}intFact1(intn){InitStack(S);PushStack(S,n);while(S.Elem[S.top]>1)PushStack(S,n-1);f=1;while(EmptyStack(S)!=True){f=f*S.Elem[S.top];PopStack(S);}},intFactorial(intn){if(n==0)return1;returnn*Factorial(n-1);},NorthChinaElectricPowerUniversity,4遞歸方程解的漸近階的求法,解遞歸方程：,T(n)=,,1若n=2,2T(n/2)+2若n>2,可以用疊代法來求解，設(shè)n=2k，且k為大于1的整數(shù)。,T(n)=2T(n/2)+2=2T(2k-1)+2=2(2T(2k-2)+2)+2=22T(k-2)+22+2=…=2k-1T(2k-(k-1))+2k-1+2k-2+…+22+2=2k-1T(2)+2k-2=2k-1+2k-2=(3/2)2k-2,代入n=2k，得T(n)=(3/2)n-2,NorthChinaElectricPowerUniversity,定理：設(shè)a,b,c是非負(fù)常數(shù)，n是c的整冪，則遞歸方程：,T(n)=,,b若n=1,aT(n/c)+bn若n>1,的解是,T(n)=,,O(n)若ac,證明：因?yàn)閚是c的整冪，可得,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,5生成函數(shù),NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,例2求斐波那契數(shù)列的通項(xiàng)Fib(n)的解析表達(dá)式。解設(shè){Fib(n)}的生成函數(shù)為G(x)=Fib(0)+Fib(1)x+Fib(2)x2++Fib(n)xn+1)xG(x)=Fib(0)x+Fib(1)x2+Fib(2)x3++Fib(n)xn+1+2)x2G(x)=Fib(0)x2+Fib(1)x3++Fib(n)xn+2+3)1)-2)-3)得：G(x)(1-x-x2)=Fib(0)+x(Fib(1)-Fib(0))+x2(Fib(2)-Fib(1)-Fib(0)+∵Fib(0)=1,Fib(1)=1∴G(x)(1-x-x2)=x,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,求一個(gè)遞歸式的非遞歸表示的一般步驟可概括為：1）設(shè)生成函數(shù)H(x)=h1x+h2x2++hnxn+使數(shù)列{hn}與要求解的遞歸式對(duì)應(yīng)。2）解H(x)為一解析式H(x)=解析表達(dá)式3）重新展開H(x)H(x)=a1x+a2x2++anxn+4）求出H(x)展開式的通項(xiàng)H(x)=這里的an就是我們要的遞歸式的非遞歸表示。,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,6遞歸樹,結(jié)點(diǎn)形式,size:表示結(jié)點(diǎn)中T的實(shí)際參數(shù),nonrec.cost:表示結(jié)點(diǎn)的非遞歸耗費(fèi),結(jié)點(diǎn)擴(kuò)展：確定一個(gè)不完全結(jié)點(diǎn)的子結(jié)點(diǎn)和非遞歸耗費(fèi)域的過程。,結(jié)點(diǎn)的擴(kuò)展方法：遞歸方程中所有含T的項(xiàng)成為它的子結(jié)點(diǎn)；2.剩余的項(xiàng)為該結(jié)點(diǎn)的非遞歸耗費(fèi)域的值。,NorthChinaElectricPowerUniversity,T(n)=T(n/2)+T(n/2)+n,T(n/2)n/2,,T(n/2)n/2,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,,,,,,,,,,,,,,,,,,,,,,,對(duì)于遞歸樹的任意一棵子樹，滿足下面的關(guān)系：,sizefieldofroot=∑nonrec.Costsofexpandednodes,+∑sizefieldsofincompletenodes.,通過遞歸樹解遞歸方程的方法：,1.首先計(jì)算遞歸樹中同一層的所有結(jié)點(diǎn)的非遞歸耗費(fèi)域之和；,2.再將剛才計(jì)算出的每一層的非遞歸耗費(fèi)域之和求和。,T(n/2)n/2,,T(n/2)n/2,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,,,,,,,,,,,,,,,,,,,,,,,n,n,n,n,,……,Θ(nlogn),NorthChinaElectricPowerUniversity,T(n-c)1,,T(n-c)1,,T(n-2c)1,,T(n-2c)1,,T(n-2c)1,,T(n-2c)1,,,,,,,,,,,,,,,,,,,,,,,,1,2,4,8,,……,Θ(2n/c),T(n)=2T(n-c)+1,NorthChinaElectricPowerUniversity,