遞歸棧的應(yīng)用課件

3.3遞歸(棧的應(yīng)用)１.遞歸的定義２.基本思想３.遞歸要素３.遞歸應(yīng)用舉例

階乘函數(shù)漢諾塔問(wèn)題３.３遞歸1、遞歸（recursion）的定義遞歸：子程序（或函數(shù)）直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己，是一種描述問(wèn)題和解決問(wèn)題的基本方法。。遞歸按其調(diào)用方式可分為直接遞歸和間接遞歸：1、直接遞歸:自己調(diào)用自己。如：voidf(n){……f(n/2);……}2、間接遞歸：P調(diào)用D，D調(diào)用P；如：voidP(intn)voidD(intn){……{……D(n/3);P(n/2);…………}}2、遞歸的基本思想問(wèn)題分解：把一個(gè)不能或不好解決的大問(wèn)題轉(zhuǎn)化為一個(gè)或幾個(gè)小問(wèn)題，再把這些小問(wèn)題進(jìn)一步分解成更小的小問(wèn)題，直至每個(gè)小問(wèn)題都可以直接解決。

3、遞歸的要素⑴遞歸邊界條件：確定遞歸到何時(shí)終止，也稱為遞歸出口；⑵遞歸模式：大問(wèn)題是如何分解為小問(wèn)題的，也稱為遞歸體。

例1、定義是遞歸的：（１）階乘函數(shù)遞歸算法longunsignedfact(intn){ if(n==0)return1;

elsereturnn*fact(n-1);}-*=時(shí)當(dāng)時(shí)當(dāng)

)!1(

1!n≥1n＝0nnn４、遞歸應(yīng)用舉例求解階乘n!的過(guò)程計(jì)算

fact(4)計(jì)算4*fact(3)計(jì)算3*fact(2)計(jì)算2*fact(1)計(jì)算fact(1)遞歸調(diào)用回歸求值返回24返回6返回2返回1（2）Fibonacci數(shù)列

0n=0Fib(n)=1n=1

Fib(n-1)+Fib(n-2)n>1011235813……遞歸算法longunsignedFib(intn){ if(n==0||n==1)returnn;//遞歸出口

elsereturnFib(n-1)+Fib(n-2);//遞歸調(diào)用}注：累計(jì)遞歸調(diào)用次數(shù)：2*Fib(n+1)-1。例２、問(wèn)題的解法是遞歸的：

利用遞歸思想來(lái)求解某類(lèi)問(wèn)題（本身沒(méi)有明顯的遞歸結(jié)構(gòu)，但操作方法可以用遞歸很好的描述）使其更為簡(jiǎn)單。如：漢諾塔問(wèn)題、背包問(wèn)題、八皇后問(wèn)題等。

（3）有的數(shù)據(jù)結(jié)構(gòu)如二叉樹(shù)、廣義表、圖等（如樹(shù)的遍歷、圖的搜索）定義。經(jīng)典問(wèn)題——漢諾塔問(wèn)題

在世界剛被創(chuàng)建的時(shí)候有一座鉆石寶塔（塔A），其上有64個(gè)金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個(gè)鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門(mén)的牧師們就一直在試圖把塔A上的碟子移動(dòng)到塔C上去，其間借助于塔B的幫助。每次只能移動(dòng)一個(gè)碟子，任何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時(shí)，世界末日也就到了。漢諾塔問(wèn)題的遞歸求解方法:如果n=1，則將這一個(gè)盤(pán)子直接從塔A移到塔C

上。否則，執(zhí)行以下三步：⑴將塔A上的n-1個(gè)碟子借助塔C先移到塔B上；⑵把塔A上剩下的一個(gè)碟子移到塔C上；⑶將n-1個(gè)碟子從塔B借助于塔A移到塔C上。

算法實(shí)現(xiàn)：voidHanoi(intn,charA,charB,charC){

if(n==1)Move(A,C);

else{

Hanoi(n-1,A,C,B);

Move(A,C);

Hanoi(n-1,B,A,C);

}

}Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)結(jié)束

漢諾塔遞歸調(diào)用過(guò)程：５、遞歸過(guò)程與遞歸工作棧非遞歸函數(shù)的調(diào)用，在函數(shù)調(diào)用前要保存以下三方面的信息：（１）返回地址（２）本函數(shù)調(diào)用時(shí)，與形參結(jié)合的實(shí)參值，包括函數(shù)名和函數(shù)參數(shù)。（３）本函數(shù)的局部變量值。遞歸函數(shù)調(diào)用也須保存這些信息，使用“遞歸工作棧”來(lái)處理?；顒?dòng)記錄：棧頂?shù)墓ぷ饔涗洷囟ㄊ钱?dāng)前正在執(zhí)行的工作記錄．遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，返回次序正好相反：遞歸調(diào)用

n!(n-1)!(n-2)!1!=1

返回次序遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。局部變量返回地址值參活動(dòng)記錄框架遞歸工作記錄⑴運(yùn)行開(kāi)始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；⑵每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；⑶每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。如：求解階乘n!，遞歸工作僅需保留４個(gè)參數(shù)：函數(shù)名fact，參數(shù)n，局部變量x（存放fact(n-1)的值）和y（存放n*fact(n-1)的值）。參見(jiàn)P103.６、消除遞歸（P103

）原因：遞歸算法時(shí)間效率較差。（１）尾遞歸和單向遞歸算法，用帶循環(huán)結(jié)構(gòu)的算法來(lái)代替。（２）用自定義棧來(lái)模擬系統(tǒng)運(yùn)行時(shí)的棧，保存相關(guān)信息，用非遞歸算法來(lái)模擬遞歸算法。實(shí)例分析：（１）尾遞歸：遞歸調(diào)用語(yǔ)句只有一個(gè)，且處于函數(shù)的最后。（可不用棧來(lái)存取相關(guān)信息）如階乘求解的非遞歸算法：longunsignedfact(intn){ longunsignedint

f=1; for(inti=1;i<=n;i++)

f=f*i; returnf;}（２）單向遞歸：各遞歸調(diào)用語(yǔ)句的參數(shù)只和主調(diào)用函數(shù)有關(guān)，相互之間參數(shù)無(wú)關(guān)，并且這些遞歸調(diào)用語(yǔ)句都處在算法的最后。如斐波那契數(shù)列非遞歸算法：longunsignedFib(intn)//用循環(huán)實(shí)現(xiàn){ if(n==0||n==1)returnn; longunsignedf1=0,f2=1,fn;

//求n>=2的情況

for(inti=2;i<=n;i++) {

fn=f1+f2; f1=f2; f2=fn; } returnfn;}時(shí)間復(fù)雜度O(n)（３）利用棧來(lái)模擬系統(tǒng)運(yùn)行時(shí)的棧漢諾塔非遞歸算法（了解）：//Datatype.h#ifndefDatatype_H#defineDatatype_HclassDatatype{public: shortint

no;

//存放一個(gè)標(biāo)識(shí)，0表示直接移動(dòng)一個(gè)圓盤(pán)

intndisk; //為1表示需進(jìn)一步分解；

charSPeg;//參數(shù)A charAPeg;//參數(shù)B charDPeg;//參數(shù)C};#endifvoidhanoi2(intn,chara,charb,charc){SeqStack<Datatype>S1;DatatypeH,H1;H.no=1;H.ndisk=n;H.SPeg=a;H.APeg=b;H.DPeg=c;

S1.Push(H);//初始入棧

while(!S1.Empty()){ if(S1.GetTop().no==1&&S1.GetTop().ndisk!=1)

{//退棧hanoi(n,a,b,c);將hanoi(n-1,a,c,b)操作參數(shù)進(jìn)棧

H.ndisk=S1.GetTop().ndisk-1; H.SPeg=S1.GetTop().SPeg; H.APeg=S1.GetTop().APeg; H.DPeg=S1.GetTop().DPeg;

S1.Pop();

H1.no=1; H1.ndisk=H.ndisk; H1.SPeg=H.APeg; H1.APeg=H.SPeg; H1.DPeg=H.DPeg;

S1.Push(H1);

//等價(jià)于move(n,a,c); H1.no=0; H1.ndisk=H.ndisk+1; H1.SPeg=H.SPeg; H1.APeg=H.DPeg;

S1.Push(H1);//等價(jià)于hanoi(n-1,b,a,c)操作參數(shù)進(jìn)棧

H1.no=1; H1.ndisk=H.ndisk; H1.SPeg=H.SPeg; H1.APeg=H.DPeg; H1.DPeg=H.APeg;

S1.Push(H1); }//處理move(n,a,c);輸出及當(dāng)只剩一個(gè)盤(pán)時(shí)的移動(dòng)信息

while((!S1.Empty())&&((S1.GetTop().no==0)||(S1.GetTop().ndisk==1)))

{//將第n個(gè)圓盤(pán)從a移到c退棧if(!S1.Empty()&&(S1.GetTop().no==0)) {

cout<<"將第"<<S1.GetTop().ndisk<<"個(gè)盤(pán)片從"

<<S1.GetTop().SPeg<<"移動(dòng)到"

<<S1.GetTop().APeg<<endl;

S1.Pop(); }

if(!S1.Empty()&&(S1.GetTop().ndisk==1)){//hanoi(1,a,b,c)退棧

cout<<"將第"<<S1.GetTop().ndisk<<"個(gè)盤(pán)片從"

<<S1.GetTop().SPeg<<"移動(dòng)到“

<<S1.GetTop().DPeg<<endl;

S1.Pop();