遞回（Recursion）

1、1 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures遞迴遞迴 (Recursion) Chapter 22 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures何謂遞迴？何謂遞迴？p定義：定義：某一函數(shù)呼叫本身即某一函數(shù)呼叫本身即遞迴遞迴。 例：計算從例：計算從1加至加至x之總和之總和 使用遞迴呼叫基本架構使用遞迴呼叫基本架構sum方法方法3 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures何謂遞迴？何謂遞迴？p條件：條

2、件：遞迴方法遞迴方法遞迴方法遞迴方法遞迴方法遞迴方法遞迴方法，計算遞迴方法，計算 1+2+31+2+3、+10+10的總和的總和4 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuressum(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

3、+8+7+6+5+4+3+2+1 =555 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures6 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures遞迴遞迴種類種類 : :B( . .); A( . .); : : 7 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures遞迴與非遞迴遞迴與非遞迴p非遞迴是不使用自已呼叫自已的方式撰寫程非遞迴是不使用自已呼叫自已的方式撰寫程式式p例例ko2_1a 非非遞迴方法，計算遞迴方法，計

4、算 1+2+3+101+2+3+10的總和的總和8 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures遞迴與非遞迴遞迴與非遞迴p主要差異在於返回資料的儲存及儲存資料記憶主要差異在於返回資料的儲存及儲存資料記憶體的需求，程式的簡明程度。體的需求，程式的簡明程度。p遞迴程式遞迴程式 優(yōu)點：程式簡潔明確，節(jié)省記憶體空間。優(yōu)點：程式簡潔明確，節(jié)省記憶體空間。 缺點：遞迴函數(shù)執(zhí)行時，因參數(shù)的存取而較缺點：遞迴函數(shù)執(zhí)行時，因參數(shù)的存取而較費時。費時。p非遞迴程式非遞迴程式 優(yōu)點：較節(jié)省執(zhí)行的時間。優(yōu)點：較節(jié)省執(zhí)行的時間。 缺點：程式較長，浪費記憶體

5、空間。缺點：程式較長，浪費記憶體空間。 9 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures遞迴樹遞迴樹Sum =1),1(1, 1xifxsumxxifp 遞迴樹遞迴樹(recursive tree)是指遞迴程式執(zhí)行的情況是指遞迴程式執(zhí)行的情況。如例題。如例題 ko2_110 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures設有一個遞迴程式如下：設有一個遞迴程式如下：fun(int n)if n=0fun(0)=0； if n=1fun(1)=1； elsefun(n)=n

6、+fun(n-1)；(a)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)求：求：(a) fun(6)之值？之值？(b)執(zhí)行執(zhí)行fun(6)之後，之後，fun( )總共被呼叫幾次總共被呼叫幾次(c)將此遞迴程式改用非遞迴程式表示。將此遞迴程式改用非遞迴程式表示。(c)非遞迴程式表示非遞迴程式表示 fun(int n) int sum=0; fo

7、r (n=0; n1p例題例題 ko2_2：使用遞迴方法，計算：使用遞迴方法，計算n!14 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures費氏數(shù)列費氏數(shù)列(Fibonacci Number)1 ，if n=1 or n=2 f(n)=f(n-1)+f(n-2)，n3例題例題ko2_3：使用遞迴方法，列出費氏數(shù)列：使用遞迴方法，列出費氏數(shù)列Note: p.30例題類似例題類似p.26底之例題，請自行參考底之例題，請自行參考下列的數(shù)列為費氏數(shù)列：下列的數(shù)列為費氏數(shù)列：11 2 3 5 8 13 21 34 55 89 144 233 以

8、數(shù)學式定義費氏數(shù)列如下：以數(shù)學式定義費氏數(shù)列如下：15 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresBinomial係數(shù)係數(shù) 1 ，if m=0 or m=nb (n，m) = b (n-1，m)+ b (n-1，m-1)，if nm0例題例題 ko2_4使用遞迴方法，計算使用遞迴方法，計算Binomial係數(shù)係數(shù)n=11, m=4為例為例mmnnmnyxmnyx0Binomial理論如下：理論如下：其中其中稱為稱為Binomial係數(shù)係數(shù)若以數(shù)學式定義若以數(shù)學式定義Binomial係數(shù)，其定義如下：係數(shù)，其定義如下：)!( !m

9、nmnmn16 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures若以數(shù)學式定義若以數(shù)學式定義Ackermanns Function如下如下m+1 ，if n=0A(n, m) = A(n-1, 1) ，if m=0 A(n-1, A(n，m-1)，if m，n0例題例題 ko2_5 使用遞迴方法，計算使用遞迴方法，計算Ackermanns FunctionAckermanns Function17 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp.33 例：例：使用遞迴方法

10、，計算使用遞迴方法，計算Ackermanns 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)= 518 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData

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

12、M(x, y)=x*y/gcd(x, y)最大公因數(shù)最大公因數(shù)19 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures質數(shù)質數(shù)p質數(shù)質數(shù)(Prime)是指除了是指除了1及本身可以整除外，及本身可以整除外，沒有其他的數(shù)可以整除。如：沒有其他的數(shù)可以整除。如：2、3、5、7、11、13p例題例題 ko2_7使用非遞迴方法求由一至該數(shù)使用非遞迴方法求由一至該數(shù)之質數(shù)之質數(shù)20 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures完美數(shù)完美數(shù)p完美數(shù)完美數(shù)(Perfect Number)是

13、指與除了本身以是指與除了本身以外所有因數(shù)之和相等的數(shù)。如：外所有因數(shù)之和相等的數(shù)。如：6的因數(shù)的因數(shù)有有1、2和和3，且，且6=1+2+3p例題例題 ko2_8使用非遞迴方法求由一至該數(shù)使用非遞迴方法求由一至該數(shù)之完美數(shù)之完美數(shù)21 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures排列組合排列組合p數(shù)字的排列數(shù)字的排列p例題例題 ko2_9輸入一字串，將其所有的輸入一字串，將其所有的排列輸出。如：輸入為排列輸出。如：輸入為123，則輸出為，則輸出為123 132 213 231 321 31222 樹德科技大學樹德科技大學 資訊管理系

14、資訊管理系 Data StructuresData Structures拉丁方陣排列拉丁方陣排列p拉丁方陣拉丁方陣(Latin Square)排列：在一個排列：在一個NXN方陣中每一列和每一行都以方陣中每一列和每一行都以1至至N的數(shù)字的數(shù)字佈滿。列與列、行與行之中都沒有相同佈滿。列與列、行與行之中都沒有相同的數(shù)字。的數(shù)字。12331223123 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures拉丁方陣排列拉丁方陣排列p解拉丁方陣的方法解拉丁方陣的方法123123312312231向後移一位向後移一位向後移一位向後移一位移向最前面移向最

15、前面移向最前面移向最前面結果結果結果結果p 例題例題 ko2_10 以非遞迴方法求拉丁方陣以非遞迴方法求拉丁方陣24 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures組合組合p數(shù)學上組合求法如下：數(shù)學上組合求法如下：程式：程式：C(n, m)if (m=0 (n=m)return 1;elsereturn C(n-1, m)+C(n-1, m-1);例題例題 ko2_11使用遞迴方法求組合公式使用遞迴方法求組合公式Cmn0,0,1111nmifCCmormnifCnmnmnm25 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Dat

16、a StructuresData Structures(一一)、大圓盤在下，小圓盤在上。、大圓盤在下，小圓盤在上。(二二)、每一次只能移動一個圓盤。、每一次只能移動一個圓盤。(三三)、圓盤只能在、圓盤只能在a、b、c圓柱上移動，圓柱上移動， 不不得超過此範圍。得超過此範圍。河內之塔河內之塔26 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures河內之塔河內之塔27 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures程式的複雜度程式的複雜度p空間複雜度：執(zhí)行程式所需要記憶體空間的大

17、小，空間複雜度：執(zhí)行程式所需要記憶體空間的大小，取決於電腦記憶體的容量。取決於電腦記憶體的容量。 程式所需佔記憶體空間分成兩類：固定和可變程式所需佔記憶體空間分成兩類：固定和可變 固定記憶體給程式中的簡單變數(shù)、結構變數(shù)及常數(shù)使用。固定記憶體給程式中的簡單變數(shù)、結構變數(shù)及常數(shù)使用。 可變記憶體是隨著程式變化而改變，如：遞迴程式儲存返回資料可變記憶體是隨著程式變化而改變，如：遞迴程式儲存返回資料的空間，結構化的變數(shù)的空間，結構化的變數(shù)p時間複雜度：時間複雜度：執(zhí)行程式所需要的時間，是考慮敘述執(zhí)行所執(zhí)行程式所需要的時間，是考慮敘述執(zhí)行所需時間及執(zhí)行的次數(shù)。將程式所有敘述所花費時間加起來，需時間及執(zhí)行

18、的次數(shù)。將程式所有敘述所花費時間加起來，就是程式時間複雜度。就是程式時間複雜度。(a)(b) for (x=0; xn; x+) (c) for (x=0; xn; x+)sum+=I ;sum+=I ; for (y=0; yn; y+) sum+=I;Sum執(zhí)行執(zhí)行 1次次n次次n2次次28 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresBig OpBig O：若且唯若：若且唯若 f(n)=O(g(n)，則存在大於，則存在大於0的的常數(shù)常數(shù)c和和n，使得對所有，使得對所有n值，若值，若nn0時，則時，則f(n)cg(n)均成立。

19、均成立。pBig O用來計算程式執(zhí)行時間的上限。用來計算程式執(zhí)行時間的上限。p例如：例如：5n+6=O(n)g(n)=n,存在大於存在大於0的的c=6和和n0=6，使對所有，使對所有n值，若值，若n6時，時， f(n)=5n+6 cg(n)=6n。隨常數(shù)。隨常數(shù)c和和n0的不同，的不同， cg(n)也改變，如也改變，如c=11和和n0=1使對所有使對所有n值，若值，若n1時，時， f(n)=5n+6 cg(n)=11n。p不論不論cg(n)值怎麼變，程式執(zhí)行的次數(shù)值怎麼變，程式執(zhí)行的次數(shù)f(n)所代表的程式所代表的程式執(zhí)行時間永遠等於執(zhí)行時間永遠等於O(n)29 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures時間時間的複雜度的複雜度 30 樹德科技大學樹德科技