遞歸程序的設(shè)計(jì)

遞歸程序的設(shè)計(jì)第1頁，共21頁，2023年，2月20日，星期四棧的應(yīng)用舉例—遞歸1遞歸的定義子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，是一種描述問題和解決問題的基本方法。

2遞歸的基本思想問題分解：把一個(gè)不能或不好解決的大問題轉(zhuǎn)化為一個(gè)或幾個(gè)小問題，再把這些小問題進(jìn)一步分解成更小的小問題，直至每個(gè)小問題都可以直接解決。

第2頁，共21頁，2023年，2月20日，星期四3遞歸的要素⑴遞歸邊界條件：確定遞歸到何時(shí)終止，也稱為遞歸出口；⑵遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。

棧的應(yīng)用舉例—遞歸第3頁，共21頁，2023年，2月20日，星期四例1階乘函數(shù)遞歸算法intfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}-*=時(shí)當(dāng)時(shí)當(dāng)

)!1(

1!n≥1n＝1nnn棧的應(yīng)用舉例—遞歸第4頁，共21頁，2023年，2月20日，星期四求解階乘n!的過程計(jì)算fact(4)計(jì)算4*fact(3)計(jì)算3*fact(2)計(jì)算2*fact(1)計(jì)算fact(1)遞歸調(diào)用回歸求值返回24返回6返回2返回1棧的應(yīng)用舉例—遞歸第5頁，共21頁，2023年，2月20日，星期四遞歸過程與遞歸工作棧遞歸過程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，返回次序正好相反：遞歸調(diào)用n!(n-1)!(n-2)!1!=1返回次序棧的應(yīng)用舉例—遞歸第6頁，共21頁，2023年，2月20日，星期四遞歸的經(jīng)典問題——漢諾塔問題

在世界剛被創(chuàng)建的時(shí)候有一座鉆石寶塔（塔A），其上有64個(gè)金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個(gè)鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動(dòng)到塔C上去，其間借助于塔B的幫助。每次只能移動(dòng)一個(gè)碟子，任何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時(shí)，世界末日也就到了。棧的應(yīng)用舉例—遞歸第7頁，共21頁，2023年，2月20日，星期四漢諾塔問題的遞歸求解:如果n=1，則將這一個(gè)盤子直接從塔A移到塔C上。否則，執(zhí)行以下三步：⑴將塔A上的n-1個(gè)碟子借助塔C先移到塔B上；⑵把塔A上剩下的一個(gè)碟子移到塔C上；⑶將n-1個(gè)碟子從塔B借助于塔A移到塔C上。

棧的應(yīng)用舉例—遞歸第8頁，共21頁，2023年，2月20日，星期四第9頁，共21頁，2023年，2月20日，星期四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);

}

}棧的應(yīng)用舉例—遞歸第10頁，共21頁，2023年，2月20日，星期四遞歸函數(shù)的內(nèi)部執(zhí)行過程每一次遞歸調(diào)用時(shí)，需要為過程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。局部變量返回地址值參活動(dòng)記錄框架遞歸工作記錄⑴運(yùn)行開始時(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í)行。棧的應(yīng)用舉例—遞歸第11頁，共21頁，2023年，2月20日，星期四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é)束第12頁，共21頁，2023年，2月20日，星期四哪些類型的問題適合于用遞歸方法求解?必須同時(shí)具備以下兩個(gè)條件：一個(gè)問題可以化解為若干個(gè)性質(zhì)相同，解法相同的小問題，而小問題還可以分解為更小的問題，……上述轉(zhuǎn)化局用相同的規(guī)律，并使問題逐步簡(jiǎn)化。當(dāng)問題規(guī)模降低到一定程度時(shí)是可以直接求解的（終止條件），即存在明確的遞歸出口。據(jù)此，以下類型的問題可以考慮采用遞歸方法求解：數(shù)學(xué)上定位為遞歸的函數(shù)數(shù)據(jù)的結(jié)構(gòu)是遞歸的例如，單鏈表，它的每個(gè)結(jié)點(diǎn)的指針域指向下一個(gè)結(jié)點(diǎn)，又是一個(gè)單鏈表；樹形結(jié)構(gòu)等等3)解題的方式用遞歸比用遞推解法簡(jiǎn)單例如，漢諾塔問題，八皇后問題等第13頁，共21頁，2023年，2月20日，星期四如何設(shè)計(jì)遞歸程序遞歸算法設(shè)計(jì)的關(guān)鍵在于,找出遞歸方程和遞歸終止條件(邊界條件).遞歸關(guān)系就是使問題向邊界條件轉(zhuǎn)化的過程.因此,遞歸關(guān)系必須能使問題越來越簡(jiǎn)單,規(guī)模越小.

因此,遞歸算法設(shè)計(jì),通常有以下3個(gè)步驟:

(1)分析問題,得出遞歸關(guān)系.

(2)設(shè)置邊界條件,控制遞歸.

(3)設(shè)計(jì)函數(shù),確定參數(shù).

第14頁，共21頁，2023年，2月20日，星期四有關(guān)遞歸的知識(shí)點(diǎn)1.什么是遞歸程序？遞歸程序的優(yōu)缺點(diǎn)是什么？它在執(zhí)行時(shí)應(yīng)借助于什么來完成？其入口語句、出口語句一般用什么語句實(shí)現(xiàn)？1)

一個(gè)函數(shù)在結(jié)束之前，直接或間接調(diào)用自身稱為遞歸。2)優(yōu)點(diǎn)：程序結(jié)構(gòu)簡(jiǎn)單、清晰，易證明其正確性。缺點(diǎn)：難以理解，執(zhí)行中占內(nèi)存空間較多，運(yùn)行效率低3)遞歸程序在執(zhí)行中需借助棧來實(shí)現(xiàn)。4)遞歸程序的入口語句和出口語句一般用條件判斷語句來實(shí)現(xiàn)。遞歸程序由基本項(xiàng)和歸納項(xiàng)組成?；卷?xiàng)是遞歸程序出口，即不再遞歸即可求出結(jié)果的部分，歸納項(xiàng)是將原來問題化成簡(jiǎn)單的且與原來形式一樣的問題，即向基本項(xiàng)發(fā)展，最終到達(dá)基本項(xiàng)。第15頁，共21頁，2023年，2月20日，星期四有關(guān)遞歸的知識(shí)點(diǎn)2.一個(gè)遞歸算法必須包括（）A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分B3.當(dāng)過程P遞歸調(diào)用自身時(shí)，過程P內(nèi)部定義的局部變量在P的2次調(diào)用期間是否占用同一數(shù)據(jù)區(qū)？為什么？答：過程P遞歸調(diào)用自身時(shí)，過程P內(nèi)部定義的局部變量在P的2次調(diào)用期間不占用同一數(shù)據(jù)區(qū)，每次調(diào)用都保留其數(shù)據(jù)區(qū)，這是由遞歸定義所決定的，用“遞歸工作?！眮韺?shí)現(xiàn)。第16頁，共21頁，2023年，2月20日，星期四有關(guān)遞歸的知識(shí)點(diǎn)4.有遞歸算法如下：intsum(intn){if(n==0)return(0);else{scanf("%d",&x);return(sum(n-1)+x)}}設(shè)初值n=4，讀入4，9，6，2。問：（1）若x為局部變量，該函數(shù)遞歸調(diào)用結(jié)束后返回調(diào)用程序的sum等于多少？畫出遞歸過程。（2）若x為全局變量，該函數(shù)遞歸調(diào)用結(jié)束后返回調(diào)用程序的sum等于多少？答：（1）sum=21,當(dāng)x為局部變量時(shí)，每次遞歸調(diào)用都要給局部變量分配存儲(chǔ)單元，故x數(shù)值4,9,6,2均保留。（2）sum=8，當(dāng)x為全局變量時(shí)，在整個(gè)程序執(zhí)行期間，X只占一個(gè)存儲(chǔ)單元，先后讀入的四個(gè)數(shù)，僅最后一個(gè)起作用，當(dāng)遞歸調(diào)用結(jié)束時(shí)，在sum:=sum(n-1)+x表達(dá)式中x就是2，所以結(jié)果為sum=2第17頁，共21頁，2023年，2月20日，星期四有關(guān)遞歸的知識(shí)點(diǎn)結(jié)果為12131215.對(duì)下面過程寫出調(diào)用P(3)的運(yùn)行結(jié)果。PROCEDUREp(w:integer);beginifw>=0thenbeginP(w-1);writeln(w);//輸出WP(w-1)end;end;6.試將下列遞推過程改寫成遞歸過程voidditui(intn){inti;i=n;while(i>1)printf(i--);}voiddigui(intn){if(n>1){printf(n);digui(n-1);}}注：該遞歸為“尾遞歸”，改成非遞歸程序時(shí)可以不使用棧。可以通過直接改變過程中的變量值，利用循環(huán)結(jié)構(gòu)代替遞歸調(diào)用第18頁，共21頁，2023年，2月20日，星期四有關(guān)遞歸的知識(shí)點(diǎn)voidtest(int&sum){Stacks;InitStack(s);intx;scanf(x);while(x!=0){push(s,x);scanf(x);}sum=0;printf(sum);while(!StackEmpty(s)){sum+=pop(s);printf(sum);}}7.將下列遞歸過程改寫為非遞歸過程voidtest(int&sum){intx;scanf(x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}

注：看程序執(zhí)行過程及結(jié)果，設(shè)輸入5310，輸出結(jié)果應(yīng)該為0149第19頁，共21頁，2023年，2月20日，星期四有關(guān)遞歸的知識(shí)點(diǎn)(1)Ack(2,1)=Ack(1,Ack(2,0))=Ack(1,Ack(1,1))=Ack(1,Ack(0,Ack(1,0)))=Ack(1,Ack(0,Ack(0,1)))=Ack(1,Ack(0,2))=Ack(1,3)=Ack(0,Ack(1,2))=Ack(0,Ack(0,Ack(1,1)))=Ack(0,Ack(0,Ack(0,Ack(1,0))))=Ack(0,Ack(0,Ack(0,Ack(0,1))))=Ack(0,Ack(0,Ack(0,2)))=Ack(0,Ack(0,3))=Ack(0,4)=58.已知Ackerman函數(shù)定義如下：習(xí)題3.27n+1,當(dāng)m=0時(shí)Ack(m,n)=Ack(m-1,1),當(dāng)m0,n=0時(shí)Ack(m-1,Ack(m,n-1)),當(dāng)m0,n0時(shí)（1）寫出Ack(2,1)的計(jì)算過程（2）寫出計(jì)算Ack(m,n)的非遞歸算法intAck(intm,intn){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,n-1)))}第20頁，共21頁，2023年，2月20日，星期四有關(guān)遞歸的知識(shí)點(diǎn)(2)intAck(intm,intn){intakm[m][n];