1、遞歸程序的設計第1頁，共21頁，2022年，5月20日，19點37分，星期三棧的應用舉例遞歸1 遞歸的定義子程序（或函數）直接調用自己或通過一系列調用語句間接調用自己，是一種描述問題和解決問題的基本方法。 2 遞歸的基本思想問題分解：把一個不能或不好解決的大問題轉化為一個或幾個小問題，再把這些小問題進一步分解成更小的小問題，直至每個小問題都可以直接解決。 第2頁，共21頁，2022年，5月20日，19點37分，星期三3 遞歸的要素 遞歸邊界條件：確定遞歸到何時終止，也稱為遞歸出口； 遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。 棧的應用舉例遞歸第3頁，共21頁，2022年，5月20日，

2、19點37分，星期三例1 階乘函數遞歸算法int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1);-*=時當時當 )!1( 1!n1n1nnn棧的應用舉例遞歸第4頁，共21頁，2022年，5月20日，19點37分，星期三求解階乘 n! 的過程計算 fact(4)計算 4*fact(3)計算 3*fact(2)計算 2*fact(1)計算 fact(1)遞歸調用回歸求值返回 24返回 6返回 2返回1棧的應用舉例遞歸第5頁，共21頁，2022年，5月20日，19點37分，星期三遞歸過程與遞歸工作棧遞歸過程在實現時，

3、需要自己調用自己。層層向下遞歸，返回次序正好相反： 遞歸調用 n! (n-1)! (n-2)! 1!=1 返回次序棧的應用舉例遞歸第6頁，共21頁，2022年，5月20日，19點37分，星期三遞歸的經典問題漢諾塔問題 在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A），其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當牧師們完成任務時，世界末日也就到了。棧的應用舉例遞歸第7頁，共21

4、頁，2022年，5月20日，19點37分，星期三漢諾塔問題的遞歸求解:如果 n = 1，則將這一個盤子直接從 塔A移到塔 C 上。否則，執(zhí)行以下三步： 將塔A上的n-1個碟子借助塔C先移到塔B上； 把塔A上剩下的一個碟子移到塔C上； 將n-1個碟子從塔B借助于塔A移到塔C上。 棧的應用舉例遞歸第8頁，共21頁，2022年，5月20日，19點37分，星期三第9頁，共21頁，2022年，5月20日，19點37分，星期三 void Hanoi(int n, char A, char B, char C) if (n=1) Move(A, C); else Hanoi(n-1, A, C, B); M

5、ove(A, C); Hanoi(n-1, B, A, C); 棧的應用舉例遞歸第10頁，共21頁，2022年，5月20日，19點37分，星期三遞歸函數的內部執(zhí)行過程每一次遞歸調用時，需要為過程中使用的參數、局部變量等另外分配存儲空間。每層遞歸調用需分配的空間形成遞歸工作記錄，按后進先出的棧組織。 局部變量返回地址值 參活動記錄框架遞歸工作記錄 運行開始時，首先為遞歸調用建立一個工作棧，其結構包括值參、局部變量和返回地址； 每次執(zhí)行遞歸調用之前，把遞歸函數的值參和局部變量的當前值以及調用后的返回地址壓棧； 每次遞歸調用結束后，將棧頂元素出棧，使相應的值參和局部變量恢復為調用前的值，然后轉向返回

6、地址指定的位置繼續(xù)執(zhí)行。棧的應用舉例遞歸第11頁，共21頁，2022年，5月20日，19點37分，星期三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,

7、B,C)結束第12頁，共21頁，2022年，5月20日，19點37分，星期三哪些類型的問題適合于用遞歸方法求解?必須同時具備以下兩個條件：一個問題可以化解為若干個性質相同，解法相同的小問題，而小問題還可以分解為更小的問題，上述轉化局用相同的規(guī)律，并使問題逐步簡化。當問題規(guī)模降低到一定程度時是可以直接求解的（終止條件），即存在明確的遞歸出口。據此，以下類型的問題可以考慮采用遞歸方法求解：數學上定位為遞歸的函數數據的結構是遞歸的例如，單鏈表，它的每個結點的指針域指向下一個結點，又是一個單鏈表；樹形結構等等3) 解題的方式用遞歸比用遞推解法簡單例如，漢諾塔問題，八皇后問題等第13頁，共21頁，202

8、2年，5月20日，19點37分，星期三如何設計遞歸程序 遞歸算法設計的關鍵在于,找出遞歸方程和遞歸終止條件(邊界條件).遞歸關系就是使問題向邊界條件轉化的過程.因此,遞歸關系必須能使問題越來越簡單,規(guī)模越小.因此,遞歸算法設計,通常有以下3個步驟:(1)分析問題,得出遞歸關系.(2)設置邊界條件,控制遞歸.(3)設計函數,確定參數.第14頁，共21頁，2022年，5月20日，19點37分，星期三有關遞歸的知識點1.什么是遞歸程序？遞歸程序的優(yōu)缺點是什么？它在執(zhí)行時應借助于什么來完成？其入口語句、出口語句一般用什么語句實現？1) 一個函數在結束之前，直接或間接調用自身稱為遞歸。2)優(yōu)點：程序結構

9、簡單、清晰，易證明其正確性。缺點：難以理解，執(zhí)行中占內存空間較多，運行效率低3)遞歸程序在執(zhí)行中需借助棧來實現。4)遞歸程序的入口語句和出口語句一般用條件判斷語句來實現。遞歸程序由基本項和歸納項組成。基本項是遞歸程序出口，即不再遞歸即可求出結果的部分，歸納項是將原來問題化成簡單的且與原來形式一樣的問題，即向基本項發(fā)展，最終到達基本項。第15頁，共21頁，2022年，5月20日，19點37分，星期三有關遞歸的知識點2.一個遞歸算法必須包括（ ） A.遞歸部分 B.終止條件和遞歸部分 C.迭代部分 D.終止條件和迭代部分B3.當過程P遞歸調用自身時，過程P內部定義的局部變量在P的2次調用期間是否占

10、用同一數據區(qū)？為什么？答：過程P遞歸調用自身時，過程P內部定義的局部變量在P的2次調用期間不占用同一數據區(qū)，每次調用都保留其數據區(qū)，這是由遞歸定義所決定的，用“遞歸工作棧”來實現。第16頁，共21頁，2022年，5月20日，19點37分，星期三有關遞歸的知識點4.有遞歸算法如下： int sum(int n) if (n=0) return(0); else scanf(%d,&x);return(sum(n-1)+x) 設初值n=4，讀入4，9，6，2。問： （1）若x為局部變量，該函數遞歸調用結束后返回調用程序的sum等于多少？畫出遞歸過程。 （2）若 x為全局變量，該函數遞歸調用結束后返

11、回調用程序的sum等于多少？答：（1）sum=21,當x為局部變量時，每次遞歸調用都要給局部變量分配存儲單元，故x數值4,9,6,2均保留。 （2）sum=8，當x為全局變量時，在整個程序執(zhí)行期間，X只占一個存儲單元，先后讀入的四個數，僅最后一個起作用，當遞歸調用結束時，在sum:=sum(n-1)+x 表達式中x就是2，所以結果為sum=2第17頁，共21頁，2022年，5月20日，19點37分，星期三有關遞歸的知識點結果為12131215.對下面過程寫出調用P(3)的運行結果。 PROCEDURE p(w:integer); begin if w=0 then begin P(w-1);

12、writeln(w);/輸出W P(w-1) end; end;6.試將下列遞推過程改寫成遞歸過程 void ditui(int n) int i; i=n; while (i1) printf(i-); void digui(int n) if (n1) printf(n); digui(n-1); 注：該遞歸為“尾遞歸”，改成非遞歸程序時可以不使用棧。可以通過直接改變過程中的變量值，利用循環(huán)結構代替遞歸調用第18頁，共21頁，2022年，5月20日，19點37分，星期三有關遞歸的知識點void test(int &sum) Stack s; InitStack(s); int x; sca

13、nf(x); while(x!=0) push(s,x); scanf(x); sum=0; printf(sum); while(!StackEmpty(s) sum+=pop(s); printf(sum); 7.將下列遞歸過程改寫為非遞歸過程 void test(int &sum) int x; scanf(x); if (x= =0) sum=0; else test(sum); sum+=x; printf(sum); 注：看程序執(zhí)行過程及結果，設輸入5 3 1 0，輸出結果應該為0 1 4 9第19頁，共21頁，2022年，5月20日，19點37分，星期三有關遞歸的知識點(1)Ac

14、k(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函數定義如下：習題3.27 n+1, 當m=0時Ack(m,n)= Ack(m-1,1), 當m0,n=0時 Ack(m-1,Ack(m,n-1), 當m0,n0時（1）寫出Ack(2,1)的計算過程（2）寫出計算Ack(m,n)的非遞歸算法int Ack(int m,int n) if(m= =0) return(n+1); else if(m!=0 & n= =0) return(Ack(m-1,1); else return(Ack(m-1,Ack(m,n-