Chapter 2 遞迴 (Recursion)

何謂遞迴？ 定義：某一函數呼叫本身即遞迴。 例：計算從1加至x之總和 使用遞迴呼叫基本架構sum方法 public static int sum(int x) { if (x= =1) return 1； else return x+sum(x-1)； }

何謂遞迴？ 不能出現無限制地呼叫自已。 條件： 遞迴方法須有初始值與最終值(即出口)。 遞迴方法須有更新值。 遞迴方法須呼叫自己。 例ko2-1：使用遞迴方法，計算 1+2+3、、+10的總和

sum(10)=10+sum(9) =10+9+ sum(8) =10+9+8+ sum(7) =10+9+8+7+ sum(6) =10+9+8+7+6+ sum(5) =10+9+8+7+6+5+ sum(4) =10+9+8+7+6+5+4+ sum(3) =10+9+8+7+6+5+4+3+ sum(2) =10+9+8+7+6+5+4+3+2+ sum(1) =10+9+8+7+6+5+4+3+2+1 =55

具有遞迴的電腦程式語 ALGOL、C、LISP、JAVA PASCAL、PL/1、PROLOG。 QBASIC、Visual Basic

遞迴種類 直接遞迴：如例ko2_1 間接遞迴：兩個以上的方法彼此呼叫對方。 Public static int A(.. ..) Public static int B(.. ..) { : { : B( .. ..); A( .. ..); : : } }

遞迴與非遞迴 非遞迴是不使用自已呼叫自已的方式撰寫程式 例ko2_1a 使用非遞迴方法，計算 1+2+3‥+10的總和

遞迴與非遞迴 主要差異在於返回資料的儲存及儲存資料記憶體的需求，程式的簡明程度。 遞迴程式 優點：程式簡潔明確，節省記憶體空間。 缺點：遞迴函數執行時，因參數的存取而較費時。 非遞迴程式 優點：較節省執行的時間。 缺點：程式較長，浪費記憶體空間。

遞迴樹 遞迴樹(recursive tree)是指遞迴程式執行的情況。如例題 ko2_1 Sum =

設有一個遞迴程式如下： fun(int n). {if. n=0. fun(0)=0；. if. n=1. fun(1)=1；. else 設有一個遞迴程式如下： fun(int n) {if n=0 fun(0)=0； if n=1 fun(1)=1； else fun(n)=n+fun(n-1)；} 求： (a) fun(6)之值？ (b)執行fun(6)之後，fun( )總共被呼叫幾次 (c)將此遞迴程式改用非遞迴程式表示。 fun(6)之值： fun(6) =6+fun(5) =6+5+fun(4) = 6+5+4+fun(3) =6+5+4+3+fun(2) = 6+5+4+3+2+fun(1) (b) 此遞迴方法呼叫順序 fun(6)->fun(5)->fun(4)->fun(3)->fun(2)->fun(1) (c) 非遞迴程式表示 fun(int n) { int sum=0; for (n=0; n<=6; n++) sum+=n; }

例：若P是一個遞迴程式，定義如下(其中x、y為正整數) P(x, y) = 求(a) P(3, 5) (b) P(17, 3) (b) P(17, 3) = P(17-3, 3) +1 = P(14, 3)+1 = P(14-3, 3) +1+1= P(11, 3)+1+1 = P(11-3, 3) +2 = P(8, 3)+2+1 = P(8-3, 3) +3 = P(5, 3) +3+ 1 = P(5-3, 3) +4+ 1 = P(2, 3) +5 =5

設有一個遞迴程式如下： fun(int n). {if. n=0. fun(0)=0；. if. n=1. fun(1)=1；. else 設有一個遞迴程式如下： fun(int n) {if n=0 fun(0)=0； if n=1 fun(1)=1； else fun(n)= fun(n-1) +fun(n-2)；} 求： fun(4)之值與遞迴樹的結構？ fun(4)之值： fun(4) = fun(3) + fun(2) = fun(2) +fun(1)+ fun(1)+ fun(0) = 3fun(1)+ 2fun(0) =3 fun(4)之遞迴樹的結構 fun遞迴程式共執行9次 ● fun(4) ● fun(3) ● fun(2) ● fun(1) ● fun(0)

階乘(n!) 1, if n≦1 n!= n*(n-1)*…*1, if n>1 例題 ko2_2：使用遞迴方法，計算n!

費氏數列(Fibonacci Number) 下列的數列為費氏數列： 1 2 3 5 8 13 21 34 55 89 144 233 … 以數學式定義費氏數列如下： 1 ，if n=1 or n=2 f(n)= f(n-1)+f(n-2)，n≧3 例題ko2_3：使用遞迴方法，列出費氏數列 Note: p.30例題類似p.26底之例題，請自行參考

Binomial係數 Binomial理論如下： 其中 稱為Binomial係數 若以數學式定義Binomial係數，其定義如下： 1 ，if m=0 or m=n b (n，m) = b (n-1，m)+ b (n-1，m-1)，if n≠m>0 例題 ko2_4使用遞迴方法，計算Binomial係數 n=11, m=4為例

Ackermann’s Function 若以數學式定義Ackermann’s Function如下 m+1 ，if n=0 A(n, m) = A(n-1, 1) ，if m=0 A(n-1, A(n，m-1))，if m，n>0 例題 ko2_5 使用遞迴方法，計算Ackermann’s Function

p.33 例：使用遞迴方法，計算Ackermann’s Function A(1, 3)之值 A(1, 3)= A(1-1, A(1,2)) = A(0, A(1-1, A(1, 2-1))) = A(0, A(0, A(1, 1))) = A(0, A(0, A(1-1, A(1, 1-1)))) = A(0, A(0, A(0, A(1, 0)))) = A(0, A(0, A(0, A(1-1, 1)))) = A(0, A(0, A(0, A(0, 1)))) = A(0, A(0, A(0, 2))) = A(0, A(0, 3)) = A(0, 4) = 5

最大公因數 最大公因數(Great Command Divisor)，用Euclid輾轉相除法求得，也就是由兩數的差與較小數的gcd求得 gcd(m-n，n), ifm>n gcd(m，n) = gcd(m，n-m), if m<n m, if n=m 輾轉相除法中的m-n改成m%n可改善其效率 m , if n=0 gcd(m，n) = gcd(n，m%n), if n≠m 例題 ko2_6 使用遞迴方法，計算最大公因數 Note: x, y的最小公倍數(LCM) LCM(x, y)=x*y/gcd(x, y)

質數 質數(Prime)是指除了1及本身可以整除外，沒有其他的數可以整除。如：2、3、5、7、11、13… 例題 ko2_7使用非遞迴方法求由一至該數之質數

完美數 完美數(Perfect Number)是指與除了本身以外所有因數之和相等的數。如：6的因數有1、2和3，且6=1+2+3 例題 ko2_8使用非遞迴方法求由一至該數之完美數

排列組合 數字的排列 例題 ko2_9 輸入一字串，將其所有的排列輸出。如：輸入為123，則輸出為 123 132 213 231 321 312

拉丁方陣排列 拉丁方陣(Latin Square)排列：在一個NXN方陣中每一列和每一行都以1至N的數字佈滿。列與列、行與行之中都沒有相同的數字。 1 2 3

拉丁方陣排列 解拉丁方陣的方法 1 2 3 1 2 3 3 1 2 2 3 1 3 1 2 例題 ko2_10 以非遞迴方法求拉丁方陣 移向最前面 1 2 3 3 1 2 結果 向後移一位 移向最前面 2 3 1 3 1 2 結果 向後移一位 例題 ko2_10 以非遞迴方法求拉丁方陣

組合 數學上組合求法如下： 程式： C(n, m) 例題 ko2_11使用遞迴方法求組合公式Cmn { if ((m==0 ｜｜(n==m)) return 1; else return C(n-1, m)+C(n-1, m-1); } 例題 ko2_11使用遞迴方法求組合公式Cmn

河內之塔 (一)、大圓盤在下，小圓盤在上。 (二)、每一次只能移動一個圓盤。 (三)、圓盤只能在a、b、c圓柱上移動， 不得超過此範圍。

河內之塔

程式的複雜度 空間複雜度：執行程式所需要記憶體空間的大小，取決於電腦記憶體的容量。 程式所需佔記憶體空間分成兩類：固定和可變 固定記憶體給程式中的簡單變數、結構變數及常數使用。 可變記憶體是隨著程式變化而改變，如：遞迴程式儲存返回資料的空間，結構化的變數 時間複雜度：執行程式所需要的時間，是考慮敘述執行所需時間及執行的次數。將程式所有敘述所花費時間加起來，就是程式時間複雜度。 (a) ‥‥ (b) for (x=0; x<n; x++) (c) for (x=0; x<n; x++) sum+=I ; sum+=I ; for (y=0; y<n; y++) ‥‥ ‥‥ sum+=I; Sum執行 1次 n次 n2次

Big O Big O：若且唯若 f(n)=O(g(n))，則存在大於0的常數c和n，使得對所有n值，若n≧n0時，則f(n)≦cg(n)均成立。 Big O用來計算程式執行時間的上限。 例如：5n+6=O(n) g(n)=n,存在大於0的c=6和n0=6，使對所有n值，若n≧6時， f(n)=5n+6 ≦cg(n)=6n。隨常數c和n0的不同， cg(n)也改變，如c=11和n0=1使對所有n值，若n≧1時， f(n)=5n+6 ≦cg(n)=11n。 不論cg(n)值怎麼變，程式執行的次數f(n)所代表的程式執行時間永遠等於O(n)

時間的複雜度 時間複雜度的大小排列順序如下： O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2 )<O(n3)<O(2n ) g(n)=1 O(1) g(n )=n O(n) g(n )=n2 O(n2 ) g(n )=n3 O(n3 ) g(n )= 2n O(2n ) g(n )=log2n O(log2n) g(n )=nlog2n O(nlog2n)

Omega(Ω) Omega(Ω)：若且唯若 f(n)=Ω (g(n))，則存在大於0的常數c和n0，使得對所有n值，若n≧n0時，則f(n) ≧ cg(n)均成立。 Omega用來計算程式執行時間的下限。 例如：5n+6= Ω(n) 程式執行次數為f(n)=5n+6= Ω(n)。g(n)=n,存在大於0的c=1和n0=1，使對所有n值，若n≧1時， f(n)=5n+6 ≧ cg(n)=5n。若n≧0時， f(n)=5n+6 ≧ cg(n)=5n仍成立。

Theta(θ) Theta：若且唯若 f(n)=θ (g(n))，則存在大於0的常數c1、 c2和n0，使得對所有n值，若n≧n0時，則c1g(n) ≦f(n) ≦ c2g(n)均成立。 g(n)既是f(n) 的上限，也是f(n) 的下限 例： 5n+6 =θ(n) 5n+6 ≧5n，當n ≧1時； 5n+6≦11n ，當n ≧1時； 故c1=5、c2=11、 n0=1，則5n+6 =θ(n)成立。