1、第 三 章 遞 歸1一個遞歸問題從前有座山，山上有座廟，廟里有個老和尚講故事，講的是從前有座山，山上有座廟，廟里有個老和尚講故事，講的是從前有座山，山上有座廟，廟里有個老和尚講故事，講的是 調用自己23.1 遞歸算法實現機制3.2 遞歸轉非遞歸(略)3.3 遞歸算法設計3.4 遞歸關系式的計算(略)目錄3遞歸 定義一個過程直接地或間接地調用自己，則稱這個過程是遞歸的過程。 遞歸算法在計算機理論和實際應用中都具有重要意義。設計和分析思路清晰，實現容易，但效率較低。43.1 遞歸算法實現機制子程序實現原理子程序調用的一般形式值回傳方式子程序調用的內部操作遞歸程序實現原理5主程序Call A1：子程

2、序 A主程序Call A2：子程序 ACall A1：(b) n次調用(a) 1次調用子程序調用的一般形式6子程序調用的一般形式Call B2：子程序 ACall A1：主程序子程序 BCall A2：子程序 ACall B1：主程序子程序 B(c)嵌套調用(d)平行調用子程序調用時，用棧方式管理調用子程序時的返回地址（包括局部變量）。7值回傳方式實參與形參的兩種數據傳送方式：值參與變參變參回傳值，有兩種方法：兩次值傳送方式按指定類型為變參設置相應的存儲空間。執行調用時，實參值傳送給變參，返回時變參值傳送給實參。地址傳送方式在內部將變參設置成一個地址，調用時將實參的地址傳送給變參。本章討論的遞

3、歸問題對變參采用兩次值傳送方式。8子程序調用的內部操作執行調用時：返回地址進棧，開辟子程序的局部變量空間為子程序準備數據，即將實參值賦值給形參指令流轉入子程序入口執行返回操作時：將變參或函數的值保存到回傳變量中從棧頂取出返回地址按地址返回將回傳變量中的值傳送給相應的變量或位置上9遞歸程序實現原理原理：一個遞歸過程的執行類似于多個子程序的嵌套調用。定義：遞歸過程直接地或間接地調用自己本身代碼。特征：有遞歸調用、有遞歸出口。特點：設計和分析思路清晰，實現容易，效率較低。10procedure f(integer n)integer y; if (n0) return 1 y f(n1); retu

4、rn(ny);end f遞歸求階乘的算法主程序：integer fn;fn f(4);11為了保證遞歸調用的正確性，需要保存調用點的現場（返回地址、局部變量、被調用函數的參數等），以便正確地返回，并且按先進后出的原則來管理這些信息。高級語言編譯程序是利用棧來實現的。 f(n) f(n1) f(n2) f(1) f(0)調用返回調用點 PnPn-1Pn-2P11調用時執行入棧操作保存現場，返回時執行出棧操作恢復現場.12計算 4 ! 遞歸過程圖示：下圖中 Pi 代表現場信息，棧元素由現場信息和參數構成f(4)4f(3) f(3)3f(2) f(2)2f(1) f(1)1f(0) f(0)1 Pu

5、sh(e4) Push(e3) Push(e2) Push(e1) f(4)4f(3) f(3) 3f(2) f(2) 2f(1) f(1) 1f(0) 24 6 2 1P4 4P3 3P4 4P2 2P3 3P4 4P1 1P2 2P3 3P4 4Pop(e1)Pop(e2)Pop(e3)Pop(e4)133.1 遞歸算法實現機制3.2 遞歸轉非遞歸3.3 遞歸算法設計3.4 遞歸關系式的計算目錄143.3 遞歸算法設計遞歸設計需滿足的要求遞歸求解的通用表現形式遞歸的幾個典型例子15遞歸設計需滿足的要求可以用遞歸求解的問題應滿足：問題P的描述涉及規模，即P(size)；規模發生變化后，問題的

6、性質不變；問題的解決有出口。 16遞歸求解的通用表現形式 Procedure P(參數表) if 遞歸出口 then 簡單操作 else 簡單操作 call P 簡單操作 endif end P規模或與規模相關的參數降低規模的處理對遞歸結果的處理17幾個典型例子簡單的0/1背包問題n階Hanoi塔問題棋子移動問題n個元素的全排列自然數拆分（正整數拆分）18例3.3 簡單的0/1背包問題 背包可容納物品的最大質量為m，現有n件物品，質量分別為m1, m2, mn，mi均為正整數，要從n件物品中挑選若干件，使放入背包的質量之和正好為m.19簡單的0/1背包問題例：m20, n5, (m1, m2,

7、 m3, m4, m5)(3,5,8,9,10) (x1,x2,x3,x4,x5)(1,0,1,1,0) m18? m28?注：對于第i件物品要么取，要么舍，不能取一部分，因此這個問題可能有解，也可能無解。布爾函數20問題分析 knap(m, n)m初始：.m1 m2 mn1 mnm.m1 m2 mn1mnmtruemnmm.m1 m2 mn1n1,即還有可選物品knap(mmn, n1)knap(m,n) knap(m,n1)knap(m,n) knap(mmn,n1)有解無解mn mm.m1 m2 mn1n1knap(m,n1)否則 false21function knap(m, n) c

8、ase :mmn0: knap true :mmn0: if n1 then if knap(mmn,n1) true then knap true else knap knap(m,n1) endif else knap false endif :mmn0:if n1 then knap knap(m,n1) else knap false ; endif endcaseEnd knap22例3.4 一個印度的古老傳說_ 漢諾塔在貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔

9、(Tower of Hanoi）。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。 假如每秒鐘一次，移完這些金片需要5845億年以上。 23n階Hanoi塔問題有n個圓盤依半徑從小到大自上而下地套在柱子A上，柱子B和C沒有圓盤。要求將A上的盤子換到C上，每次只移動一個，且不允許將大圓盤壓在小圓盤的上面。24XYZHanoi(n,X,Y,Z)圓盤數量源柱輔助柱目標柱尋找遞歸出口(1) n1, X1Z(2) n2,

10、 X1Y X2Z Y1Z25n階Hanoi問題Hanoi(n,X,Y,Z)n3, Hanoi(2,X,Z,Y) XZ Hanoi(2,Y,X,Z)3XYZ26CABCABABC(1) Hanoi(n1,X,Z,Y)(2) X nZ(3) Hanoi(n1,Y,X,Z)XYZHanoi(n,X,Y,Z)圓盤數量源柱輔助柱目標柱27n階Hanoi問題procedure Hanoi(n, X, Y, Z) if (n1) then move(X, Z) else Hanoi(n1, X, Z, Y) move(X, Z) Hanoi(n1, Y, X, Z) endifEnd Hanoi28例3.5

11、 棋子移動問題 有2n個棋子(n4)排成一行，白子用0表示，黑子用1表示，例如n5時初始狀態為右邊至少有兩個空位）0 0 0 0 0 1 1 1 1 1 _ _，（要求通過棋子移動最終成為 0 1 0 1 0 1 0 1 0 1.29棋子移動問題移動規則每次必須同時移動相鄰兩個棋子顏色不限，移動方向不限每次移動必須跳過若干棋子不能調換這兩個棋子的位置30n4 00001111_ _ step1 000_ _11101 (4,5)(9,10) step2 0001011_ _1 (8,9)(4,5) step3 0_ _1011001 (2,3)(8,9) step4 010101_ _01 (

12、7,8)(2,3) step5 _ _01010101 (1,2)(7,8)尋找遞歸出口31n5 0000011111_ _ step1 0000_ _111101 (5,6)(11,12) step2 00001111_ _01 (9,10)(5,6)n6 000000111111_ _ step1 00000_ _1111101 (6,7)(13,14) step2 0000011111_ _01 (11,12)(6,7)chess(n)遞歸出口：n4;遞歸過程：n4時；move (n,n1)(2n1,2n2)；move (2n1,2n)(n,n1);call chess(n1); 32棋

13、子的移動問題Procedure Chess(n) if n=4 then move (4,5) (9,10) move (8,9) (4,5) move (2,3) (8,9) move (7,8) (2,3) move (1,2) (7,8) else move (n, n+1) (2n+1, 2n+2) move (2n1, 2n) (n, n+1) call Chess(n-1) endifEnd Chess遞歸出口遞歸調用A(9)A(4)A(10)A(5)33例3.6 求n個元素的全排列設A=a1,a2,an是要進行排列的n個元素的集合， n1 輸出a1 n2 輸出a1a2 a2a1

14、n3 輸出a1a2a3 a1a3a2 a2a1a3 a2a3a1 a3a2a1 a3a1a2 分析n3，排列按如下步驟進行： a1之后跟a2, a3的所有全排列；在上述全排列里，a1和a2位置互換；在上述全排列里， a1和a3位置互換。34求n個元素的全排列range(A) = a1range(A1), a2range(A2), anrange(An)集合A用數組實現range(A,1,n)：遞歸出口：range(A, n, n)遞歸調用：使得集合所有元素都可以作為前綴出現A-a1A-a2A-an35求n個元素的全排列procedure range(A, k, n) if kn then pr

15、int(A) else for i k to n do A(k) A(i) call range(A,k1,n) A(k) A(i) repeat endifend range遞歸出口，打印整個數組A。A(i)與A(k)值互換缺省時，認為形參是in型，其值變化時不回傳。call range(A,1,n)36range(A,1,3)If 13 then print(A) else for i 1 to 3 do A(1)A(i); call range(A,2,3) 略A=a, b, cabc1) i1, aa Aa,b,c2) i2, bb Aa,b,cacb3) i3, bc Aa,c,bb

16、ac4) i2, a b Ab,a,c5) i2, aa Ab,a,cbca6) i3, ac Ab,c,arange(A,2,3)for i2 to 3 do A(2)A(i); call range(A,3,3) 略range(A,3,3)If 33 print(A) 略7) i3, ac Ac,b,acba8) i2, bb Ac,b,acab9) i3, ba Ac,a,b37例3.7 自然數拆分任何一個大于1的自然數n，總可以拆分成若干個小于n的自然數之和，試求n的所有拆分。n2 211n3 312 111n4 413 112 1111 2238自然數拆分（正整數拆分）n6 6 15

17、 114 1113 11112 111111 1122 123 24 222 3339自然數拆分（正整數拆分）拆分的結果用一維數組A保存；對任意自然數的所有拆分方式，依據A(1)的值，可以分為n/2類；第i類第一行元素是A1i， A2ni；為保證拆分不重復，A中元素是非降的；下一次的拆分，用A的下標來控制，而不是A中的元素值；發生下一次拆分（遞歸調用）的判斷條件。40自然數拆分（正整數拆分）算法procedure split(t) for k 1 to t do write(A(k) ; repeat j t; L A(j) for i A(j1) to L/2 do A(j) i; A(j1

18、) Li ; call split(t1) repeat end split procedure main(n) for i 1 to n2 do A(1) i; A(2) ni; call split(2) repeatend main輸出已產生的一種拆分本次拆分的起始位置本次拆分的數值41split(2)Print:1,3j2; L3i在13/2之間i1: A2 1; A3 2;main(4)i在14/2之間i1: A11; A23;i2: A12; A22;1split(3)Print:1,1,2j3; L2i在12/2之間i1: A3 1; A4 12split(4)Print:1,1

19、,1,1j4; L1i在11/2之間3split(2)Print:2,2j2; L3i在22/2之間4423.4 遞歸關系式的計算遞歸算法的時間復雜度分析K階線性齊次遞歸關系式的解法 43遞歸算法的時間復雜度分析求n個元素的最大元問題 二分法 Max(A,1,n) A(1)A(2) A(n/2) A(n/21) A(n)Max(A,1, n/2)Max(A,n/21,n)max44求n個元素的最大元問題Procedure MAX (A,i, j) if ij then return A(i) endif if ji1 then if A(i)A(j) then return A(i) else return A(j) ; endif else k (ij)/2 m1 MAX(