1、第一章 數學預備知識 第二章 導引與基本數據結構第三章 遞歸算法武漢科技大學理學院信息與計算科學系楊 波cookie_2008年9月2008-09-01版權所有：楊波，武漢科技大學理學院 遞歸遞歸是一種強有力的設計方法遞歸的效率問題遞歸的實現機制執行調用時將返回地址進棧為遞歸子程序準備數據：實參形參值將指令流轉入新一級子程序入口處2008-09-01版權所有：楊波，武漢科技大學理學院 執行返回時保存中間計算結果數據從棧頂取出返回地址值按返回地址返回若有變參或函數，進行參數或函數回傳遞歸的滿足要求問題P的描述涉及到規模規模發生變化時，問題的性質不發生變化問題的解決有出口，即遞歸有結束的條件200

2、8-09-01版權所有：楊波，武漢科技大學理學院 遞歸的表現int P(參數表) if (遞歸出口) 簡單操作 else 簡單操作; P; 簡單操作; 初始情況遞歸部分2008-09-01版權所有：楊波，武漢科技大學理學院 階乘函數階乘函數定義為：public int Factorial(int n) if(n=0) return 1; return n*Factorial(n-1); 2008-09-01版權所有：楊波，武漢科技大學理學院 斐波那契（Fibonacci）數列 無窮數列1,1,2,3,5,8,13,稱為Fibonacci數列，遞歸定義為： public int F(int n)

3、 if(n=1) return 1; return F(n-1)+F(n-2);時間復雜度：指數階F(5)= F(4) + F(3) = (F(3) + F(2) + (F(2) + F(1) = (F(2) + F(1) + (F(1) + F(0) + (F(1) + F(0) +1) = (F(1) + F(0) + 1) + (1 +1) +(1 + 1) +1) 2008-09-01版權所有：楊波，武漢科技大學理學院 歐幾里德算法求最大公因子算法定義為： public static int GCD(int a,int b) if(b=0) /遞歸結束條件 return a; retu

4、rn GCD(b,a%b); /遞歸執行部分GCD(22,8)=GCD(8,22%8)=GCD(8,6)=GCD(6,8%6)=GCD(6,2)=GCD(2,6%2)=GCD(2,0)=22008-09-01版權所有：楊波，武漢科技大學理學院 已知元素x，判斷x是否在a1:n中 public static void main(String argv) int x; int a; a=new int5; for(int i=1;in) return 0; else if(aj=x) return j; else return Search(j+1,x,a); 2008-09-01版權所有：楊波，

5、武漢科技大學理學院 整數劃分問題將正整數n表示成一系列正整數之和，n=n1+n2+nk，其中n1n2nk1，k1。正整數n的這種表示稱為正整數n的劃分。正整數n的不同劃分個數稱為正整數n的劃分數，記作p(n)。 例如：正整數6有如下11中不同的劃分，所以p(6)=11。6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。 2008-09-01版權所有：楊波，武漢科技大學理學院 在正整數n的所有不同的劃分中，將最大加數n1不大于m的劃分個數記作q(n,m)。可以建立q(n,m)的如下遞歸關系。 q(n,1)=

6、1, n11q(n,m)=q(n,n), mn q(n,n)=1+q(n,n-1) q(n,m)=q(n,m-1)+q(n-m,m), nm1 當最大加數n1不大于1時，任何正整數n只有一種劃分形式，即 1+1+1+1最大數n1實際上不能大于n。因此，q(1,m)=1正整數n的劃分由n1=n的劃分和n1n-1的劃分組成 正整數n的最大加數n1不大于m的劃分由n1=m的劃分和n1m-1的劃分組成 6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。 2008-09-01版權所有：楊波，武漢科技大學理學院 pu

7、blic static int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) return q(n,n); if(n=m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); 2008-09-01版權所有：楊波，武漢科技大學理學院 消去遞歸直接遞歸消去規則（包括兩方面）將遞歸過程中出現遞歸的地方，用等價的非遞歸代碼來代替（后面將給出的規則1-7）對return語句做適當處理（后面將給出的規則8-13）2008-09-01版權所有：楊波，武漢科技大學理學院 消去規則消去

8、遞歸調用過程的開始部分，插入說明為棧的代碼并將其初始化為空。（在一般情況下，棧用來存放參數、局部變量、函數的值，和每次遞歸調用的返回地址。） 將標號Li附于第一條可執行語句。然后，對于每一處遞歸調用都用一組執行下列規則的指令來代替。 將所有參數和局部變量的值存入棧。棧頂指針可作為一個全局變量來看待。 建立第i個新標號Li，并將i存入棧。這個標號的i值將用來計算返回地址。此標號放在規則7所描述的程序段中。 計算本次調用的各實在參數（可能是表達式）的值，并將這些值賦給相應的形式參數。 插入一條無條件轉向語句轉向過程的開始部分。 如果這過程是函數，則對遞歸過程中含有此次函數調用的那條語句作如下處理：

9、將該語句的此次函數調用部分用從棧頂取回該函數值的代碼來代替，其余部分的代碼按原描述方法照抄，并將4中建立的標號附于這條語句上。如果此過程不是函數，則將4建立的標號附于6所產生的轉移語句后面的那條語句。 2008-09-01版權所有：楊波，武漢科技大學理學院 對return語句的處理如果棧為空，則執行正常返回。 否則，將所有輸出參數的當前值賦給棧頂上的那些對應的變量。 棧中有返回地址標號的下標，就插入一條此下標從棧中退出的代碼，并把這個下標賦給一個未使用的變量。 從棧中退出所有局部變量和參數的值并把它們賦給對應的變量。 如果這個過程是函數，則插入以下指令，這些指令用來計算緊接在return后面的

10、表達式并將結果值存入棧頂。 用返回地址標號的下標實現對該標號的轉向。2008-09-01版權所有：楊波，武漢科技大學理學院 求數組中的最大元素A1:n2008-09-01版權所有：楊波，武漢科技大學理學院 int Max1(int i) int j,k; if(iaj) k=i; else k=j; else k=a.length-1; return k;public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數組a中存放了待查詢的元素 stack=new int2*n+1; /規則1 to

11、p=0; /規則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規則8 else /規則9 addr=stacktop;top=top-1; /規則10 i=stacktop;top=top-1; /規則11 top=top+1;stacktop=k; /規則12 if(addr=2) go to L2 /規則13 規則1：過程的開始部分，插入說明為棧的代碼并將其初始化為空。（在一般情況下，棧用來存放參數、局部變量、函數的值，和每次遞歸調用的返回地址。）規則2：將標號Li附于第一條可執行語句。然后，對于每一處遞歸調用都用一組

12、執行下列規則的指令來代替。規則3：將所有參數和局部變量的值存入棧。棧頂指針可作為一個全局變量來看待。 規則4：建立第i個新標號Li，并將i存入棧。這個標號的i值將用來計算返回地址。此標號放在規則7所描述的程序段中。 規則5：計算本次調用的各實在參數（可能是表達式）的值，并將這些值賦給相應的形式參數。 規則6：插入一條無條件轉向語句轉向過程的開始部分。 規則7：如果這過程是函數，則對遞歸過程中含有此次函數調用的那條語句作如下處理：將該語句的此次函數調用部分用從棧頂取回該函數值的代碼來代替，其余部分的代碼按原描述方法照抄，并將4中建立的標號附于這條語句上。如果此過程不是函數，則將4建立的標號附于6

13、所產生的轉移語句后面的那條語句。 規則8：如果棧為空，則執行正常返回。 規則10：棧中有返回地址標號的下標，就插入一條此下標從棧中退出的代碼，并把這個下標賦給一個未使用的變量。 規則11：從棧中退出所有局部變量和參數的值并把它們賦給對應的變量。 規則12：如果這個過程是函數，則插入以下指令，這些指令用來計算緊接在return后面的表達式并將結果值存入棧頂。 規則13：用返回地址標號的下標實現對該標號的轉向。 規則9：否則，將所有輸出參數的當前值賦給棧頂上對應的那些變量2008-09-01版權所有：楊波，武漢科技大學理學院 012345678910public int Max2(int i) /

14、java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數組a中存放了待查詢的元素 stack=new int2*n+1; /規則1 top=0; /規則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規則8 else addr=stacktop;top=top-1; /規則10 i=stacktop;top=top-1; /規則11 top=top+1;stacktop=k; /規則12 if(addr=2) go to L2 /規則13 例：求數組a1:5中最大元素

15、的算法，a1=3，a2=10，a3=8，a4=9，a5=412223224k=5addr=2i=45j=5k=4i=34j=4i=24k=2i=12j=22008-09-01版權所有：楊波，武漢科技大學理學院 改進1上述算法只是為了說明一般方法。 對于棧的處理實際上可以采用結構體或類的方式實現，上述stack中分別存放了參數值或者函數返回值和每次函數調用的返回地址（實際為標號的下標，在此均為2）。可以使用二維數組來實現堆棧。 2008-09-01版權所有：楊波，武漢科技大學理學院 public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n

16、,top; n=a.length()-1; /數組a中存放了待查詢的元素 stack=new intn+12; /規則1 top=0; /規則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規則8 else addr=stacktop1; /規則10 i=stacktop0; /規則11 stacktop0=k; /規則12 if(addr=2) go to L2 /規則13 public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()

17、-1; /數組a中存放了待查詢的元素 stack=new int2*n+1; /規則1 top=0; /規則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規則8 else addr=stacktop;top=top-1; /規則10 i=stacktop;top=top-1; /規則11 top=top+1;stacktop=k; /規則12 if(addr=2) go to L2 /規則13 2008-09-01版權所有：楊波，武漢科技大學理學院 改進2由于過程只返回一個地方，所以不必重復存放返回地址。也不需要轉向語句。

18、 2008-09-01版權所有：楊波，武漢科技大學理學院 public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數組a中存放了待查詢的元素 stack=new intn+1; top=0; while(iaj) k=i; else k=j; return k; public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數組a中存放了待查詢的元素 stack=new int2*n+1; /規則1 top=0; /規則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規則8 else addr=stacktop;top=top-1; /規則10 i=stacktop;to