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

《遞歸程序的設(shè)計(jì)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、棧的應(yīng)用舉例—遞歸1遞歸的定義子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，是一種描述問題和解決問題的基本方法。2遞歸的基本思想問題分解：把一個不能或不好解決的大問題轉(zhuǎn)化為一個或幾個小問題，再把這些小問題進(jìn)一步分解成更小的小問題，直至每個小問題都可以直接解決。3遞歸的要素⑴遞歸邊界條件：確定遞歸到何時(shí)終止，也稱為遞歸出口；⑵遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。棧的應(yīng)用舉例—遞歸例1階乘函數(shù)遞歸算法intfact(intn){if(n==0)return1;elseret

2、urnn*fact(n-1);}-*=時(shí)當(dāng)時(shí)當(dāng))!1(1!n≥1n＝1nnn棧的應(yīng)用舉例—遞歸求解階乘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)用舉例—遞歸遞歸過程與遞歸工作棧遞歸過程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，返回次序正好相反：遞歸調(diào)用n!(n-1)!(n-2)!1!=1返回次序棧的應(yīng)用舉例—遞歸遞歸的經(jīng)典問題——漢諾塔問題在世界剛被創(chuàng)建的時(shí)候有一座鉆石寶塔（塔A），其

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

4、個碟子從塔B借助于塔A移到塔C上。棧的應(yīng)用舉例—遞歸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)用舉例—遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過程每一次遞歸調(diào)用時(shí)，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。局部變量返回地址值參活動記錄框架遞歸工作記錄⑴運(yùn)行開始時(shí)，首先為遞歸調(diào)用建立

5、一個工作棧，其結(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)用舉例—遞歸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,

6、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é)束哪些類型的問題適合于用遞歸方法求解?必須同時(shí)具備以下兩個條件：一個問題可以化解為若干個性質(zhì)相同，解法相同的小問題，而小問題還可以分解為更小的問題，……上述轉(zhuǎn)化局用相同的規(guī)律，并使問題逐步簡化。當(dāng)問題規(guī)模降低到一定程度時(shí)是可以直接求解的（終止條件），即存在

7、明確的遞歸出口。據(jù)此，以下類型的問題可以考慮采用遞歸方法求解：數(shù)學(xué)上定位為遞歸的函數(shù)數(shù)據(jù)的結(jié)構(gòu)是遞歸的例如，單鏈表，它的每個結(jié)點(diǎn)的指針域指向下一個結(jié)點(diǎn)，又是一個單鏈表；樹形結(jié)構(gòu)等等3)解題的方式用遞歸比用遞推解法簡單例如，漢諾塔問題，八皇后問題等如何設(shè)計(jì)遞歸程序遞歸算法設(shè)計(jì)的關(guān)鍵在于,找出遞歸方程和遞歸終止條件(邊界條件).遞歸關(guān)系就是使問題向邊界條件轉(zhuǎn)化的過程.因此,遞歸關(guān)系必須能使問題越來越簡單,規(guī)模越小.因此,遞歸算法設(shè)計(jì),通常有以下3個步驟:??????(1)分析問題,得出遞歸關(guān)系.???

8、???(2)設(shè)置邊界條件,控制遞歸.??????(3)設(shè)計(jì)函數(shù),確定參數(shù).有關(guān)遞歸的知識點(diǎn)1.什么是遞歸程序？遞歸程序的優(yōu)缺點(diǎn)是什么？它在執(zhí)行時(shí)應(yīng)借助于什么來完成？其入口語句、出口語句一般用什么語句實(shí)現(xiàn)？1)一個函數(shù)在結(jié)束之前，直接或間接調(diào)用自身稱為遞歸。2)優(yōu)點(diǎn)：程序結(jié)構(gòu)簡單、清晰，易證明其正確性。缺點(diǎn)：難以理解，執(zhí)行中占內(nèi)存空間較多，運(yùn)行效率低3)遞歸程序在執(zhí)行中需借助棧來實(shí)現(xiàn)。4)遞歸程序的入口語句和出口語句一般用條件判斷語句來實(shí)現(xiàn)。遞歸程序由基