Course 2 遞迴 Recursion

▓ Outlines 本章重點 Def.與種類 Recursion與Non-recursion的比較 設計方式 遞迴演算法則的複雜度分析 數學解法 (Mathematics-based method) 替代法 (Substitution method) 遞迴樹法 (Recursion tree method) 支配定理法 (Master theorem method)

▓ Recursion Algorithm 一般來說，有兩種方式可以撰寫具有重覆執行 (Repetitive)特性的演算法: Iteration (迴圈) Recursion (遞迴) Def: algorithm 中含有self-calling (自我呼叫)敘述存在。

遞迴的種類: 直接遞迴 (Direct Recursion): 間接遞迴 (Indirect Recursion): 函式或程序直接呼叫本身時稱之。 間接遞迴 (Indirect Recursion): 函式或程序先呼叫另外的函式，再從另外函式呼叫原來的函式稱之。 void Function2(void) { …….. Function2( ); } void Function1(void) { …….. Function2( ); } void Function2(void) { …….. Function1( ); }

尾端遞迴 (Tail Recursion): 屬於直接遞迴的特例 建議：用非遞迴方式會較有效率 即: 改用迴圈 (while…, repeat…until) ∵遞迴要花費額外的處理 (如: stack的push, pop,…) void Function2(void) { …….. Function2( ); } 程式結束 的前一行

▓ 遞迴演算法則的設計 找出問題的終止條件. 找出問題本身的遞迴關係. 遞迴的架構: if (終止條件) then 結束遞迴，需要時回傳結果 else (遞迴關係)

階乘 (Factorial; n!) We can define 終止條件 遞迴關係

Recursive Factorial Algorithm inputs: n is the number being raised factorially outputs: n! is returned Procedure Factorial(int n) begin if (n = 0) return 1; else return (n Factorial(n-1)); end

Ex: Factorial(3) = ? 呼叫了幾次函數？ Factorial(3) = 3  Factorial(2) Factorial(3) = 3  2 = 6 Factorial(2) = 2  Factorial(1) Factorial(2) = 2  1 = 2 Factorial(1) = 1  Factorial(0) Factorial(1) = 1  1 = 1 Factorial(0) = 1 呼叫了4次 (含Factorial(3))，結果為6 Factorial(n)會被呼叫幾次？ 呼叫n+1次

Write a program in C++ int Factorial(int n) { if (n==0) return (1); else return (n*Factorial(n-1)); }

Iterative Factorial Algorithm inputs: n is the number being raised factorially outputs: n! is returned void Factorial(int n) { factN = 1; for (i=1, i ≤ n, i++) factN = factN * i; return factN; }

費氏數 (Fibonacci Number) Ex: 觀念: F0 + F1  F2 F1 + F2  F3 F2 + F3  F4 F3 + F4  F5 n 1 2 3 4 5 6 7 8 9 10 Fn 13 21 34 55  Fa + Fb  Fc

Recursive Algorithm Definition 終止條件 遞迴關係

Recursive Fibonacci Algorithm inputs: num identified the ordinal of the Fibonacci number outputs: returns the nth Fibonacci number void Fib(int num) { if (num is 0 OR num is 1) return num; else return (Fib(num-1) + Fib(num-2)); }

Based on recursive function, 求Fib (4) 共呼叫此函數幾次? (含Fib(4))  Ans: 9次

Iterative Fibonacci Number Algorithm inputs: num identified the ordinal of the Fibonacci number outputs: returns the nth Fibonacci number void Fib(int num) { if (num is 0 OR num is 1) return num; else { Fa = 0, Fb = 1; for(i = 2, i<=num, i++) Fc = Fa + Fb; Fa = Fb; Fb = Fc; end for; return Fc; }; } C++ Program: int Fib(int n) { if (n <= 1) return n; else { int Fa=0, Fb=1, Fc, i; for(i=2; i<=n; i++) Fc = Fa + Fb; Fa = Fb; Fb = Fc; }; return Fc; }

二項式係數 Binomial Coefficient 或稱組合問題 (Combination of n objects) Recursive Algorithm Definition 終止條件 遞迴關係

Find the result of Bin(5,3) and how many invocation of Bin Find the result of Bin(5,3) and how many invocation of Bin? (including Bin(5,3)) 呼叫 19次 結果為 10 1 1 1 1 1 1 1 1 1 1

Recursive Binomial Coefficient Algorithm inputs: 輸入二項式的n與m outputs: 傳回二項式計算結果 void Bin(int n, int m) { if (n=m or m=0) return 1; else return (Bin(n-1, m) + Bin(n-1, m-1)); }

▓ Recursion 與 Non-recursion 的比較 優 程式較精簡 冗長 缺 區域變數極少使用 較多 節省Storage空間 浪費Storage 表達力強，易於理解 表達力差，不易理解 需要額外的Dynamic Stack空間支援 不需要 執行效益較差。 ∵需要花費額外時間做: Push參數, 區域變數, 返回位址 in to stack 控制權轉移 Pop stack 較優

How Recursion Works Push Pop Stack 參數 變數 位址 void Function1(void) { …….. Function2( ); } void Function2(void) { …….. End; }    Push Pop 參數 變數 位址 Stack

要保存Function1當時執行的狀況，即Push下列資料到Stack中。 參數值 (Parameter) 區域/暫存變數值 (Local Variable) 返回位址 (Return Address) 要做控制權轉移 (Jump to Function2) Recursion動作結束時，要Pop Stack，以取出參數、區域/暫存變數值及返回位址 ，then goto “Return Address”。 Push, Jump, Pop皆耗時，效率差 Recursion與Non-recursion的程式可以互相改寫!!

Note: 可自行回答下列問題，若有一個回答為“no”，則 你不應使用遞迴來設計演算法: 演算法所處理的問題或是資料結構本身合乎遞迴的特性嗎 (Is the algorithm or data structure naturally suited to recursion)? 若用了遞迴是否可使結果更小及更易了解 (Is the recursive solution shorter and more understandable)? 這個遞迴結果的執行是在可接受的執行時間和空間限制嗎 (Does the recursive solution run in acceptable time and space limits)?

▓ 遞迴演算法則的複雜度分析 遞迴演算法的分析比iterative algorithm的分析要來得困難。 分析步驟: 我們找出遞迴演算法的遞迴方程式 T(n) (recurrence equation, 或通稱為Time function, Complexity function亦可) 來表達該演算法的執行次數。 接著，解這個遞迴方程式來求出該演算法的時間複雜度。

以 “Factorial” 為例，透過對遞迴關係與終止條件的分析，我們可以得知Factorial遞迴演算法的遞迴方程式 (時間函數) 如下: T(n) = T(n-1) + 1 前 n-1 次遞迴呼叫次數 第 n 次乘法的執行次數 (也可寫成 c 表示某一常數) 每一次遞迴呼叫時所會花費的成本

以 “Fibonacci” 為例，透過對遞迴關係與終止條件的分析，我們可以得知Fibonacci遞迴演算法的遞迴方程式 (時間函數) 如下: T(n) = T(n-1) + T(n-2) + 1 最頂層 一 次加法的執行次數 (也可寫成 c 表示某一常數) 每一次遞迴呼叫時所會花費的成本 兩個不同遞迴呼叫的次數

通常在討論遞迴演算法時，我們常會一起將這些演算法的遞迴方程式列出。因此，本單元假設遞迴方程式已給定，主要議題則設定在如何解遞迴方程式。 遞迴方程式的解法與使用時機: 解法 使用時機 替代法 (Substitution Method) 已知Answer時 遞迴樹法 (Recursion-tree Method) 母問題由多個子問題所構成時 支配理論 (Master Theorem Method) 遞迴方程式為特定型式時 數學解法 (Mathematics-based Method) 逼不得已時

▓ 數學解法 (Mathematics-based Method) 即課本附錄B.3的代入法 (Substitution, 意義不同於後面介紹的Substitution Method (替代法)) 直接將遞迴方程式以遞迴的觀念由最末項往前求解，然後整理出答案。

範例 1 請利用數學解法找出下列遞迴方程式 (時間函數) 的時間複雜度。 T(n) = T(n-1) + n T(1) = 1 Sol: = (T(n-2) + (n-1)) + n = T(n-2) + (n-1) + n = (T(n-3) + (n-2)) + (n-1) + n = T(n-3) + (n-2) + (n-1) + n … = T(1) + 2 + 3 + … + (n-2) + (n-1) + n = 1 + 2 + 3 + … + (n-2) + (n-1) + n  T(n) = n(n+1)/2 前 n-1 次遞迴呼叫次數 最頂層工作的執行次數 每一次遞迴呼叫時所會花費的成本 時間複雜度: O(n2)

若有一個時間函數 其中 T(2) = 1，求T(n) = ? Big-O =? Sol: = T(n1/2) + 1 範例 2 若有一個時間函數 其中 T(2) = 1，求T(n) = ? Big-O =? Sol: = T(n1/2) + 1 = [T(n1/4) + 1] + 1 = T(n1/4) + 2 = [T(n1/8) + 1] + 2 = T(n1/8) + 3 = … = T(n1/2i) + i (想辦法讓 n1/2i 等於 2，以使T(2)=1) = T(2) + log2 log2 n = 1 + log2 log2 n  令n1/2i = 2, 等號兩邊取log2, 則 1/2i log2 n = log22 = 1  log2 n = 2i, 等號兩邊再取log2  log2 log2 n = i  O(log2 log2n)

範例練習 Example B.22

▓ 替代法 (Substitution Method) 即課本附錄B.1的歸納法 (Induction)之應用 適用於檢驗某個候選解答是否為此遞迴演算法的正確解，而不適用於求遞迴方程式的解答。 使用步驟: 利用猜測、觀察或匯整的方式，找出遞迴方程式的解 (最難!!) 利用數學歸納法証明此解是正確的 由於利用此方法求解遞迴方程式，最難的地方就是如何去猜出、觀察出或匯整出遞迴方程式的解。所以一般只適合當已有候選解時，用來驗証該解是否正確，也就是為了避開第一個步驟。

範例 1 請利用替代法找出 “Factorial” 的時間複雜度。Factorial的遞迴方程式 (時間函數) 如下: T(n) = T(n-1) + 1 T(0) = 0 Sol: 利用猜測、觀察或匯整的方式，找出遞迴方程式的解 已知終止條件為T(0) = 0，我們可以嘗試匯整T(n)如下: T(1) = T(1-1) + 1 = T(0) + 1 = 1 T(2) = T(2-1) + 1 = T(1) + 1 = 2 T(3) = T(3-1) + 1 = T(2) + 1 = 3 … T(n) = n

利用數學歸納法証明 T(n) = n 是正確的 數學歸納法的步驟: 找出歸納基底: 對於n=0, T(0) = 0 找出歸納步驟: 我們必須証明 T(n+1) = n + 1 Proof: T(n+1) = T(n+1-1) + 1 = T(n) +1 = n + 1 (  ) (  )

範例 2 請利用替代法找出下列遞迴方程式的時間複雜度。 T(n) = 2T(n/2) + n – 1, for n > 1, n a power of 2 T(1) = 0 Sol: 利用猜測、觀察或匯整的方式，找出遞迴方程式的解 已知終止條件為T(1) = 0，我們嘗試匯整T(n)如下: T(2) = 2T(2/2) + 2 - 1 = 2T(1) + 1 = 1 T(4) = 2T(4/2) + 4 - 1 = 2T(2) + 3 = 5 T(8) = 2T(8/2) + 8 - 1 = 2T(4) + 7 = 17 T(16) = 2T(16/2) + 16 - 1 = 2T(8) + 15 = 49 … T(n) = ??? (難匯整)

範例練習 課本附錄B之Example B.1, Example B.2

▓ 遞迴樹法 (Recursion-tree Method) 適用於母問題由多個子問題所構成 使用一個樹狀結構表示遞迴演算法則在執行過程被遞迴呼叫的情況，這個樹狀結構稱為遞迴樹。其中: Node: 存放遞迴關係式所相對應之子問題的Cost Degree: 子問題的數目 遞迴樹法的三個步驟: 按照遞迴方程式展開 對每一層的所有子問題之cost加總，得到每一層之cost 加總每一層的cost，以得到total cost，即為答案 通常只能求出Big-O或，若要計算  得用“夾擠”法

若要計算  得用“夾擠法”，分別計算O和 範例 1 若遞迴式T(n) = T(n/2) + T(n/4) + T(n/8) + n，試求T(n) = (n)。(94成大) Sol: 若要計算  得用“夾擠法”，分別計算O和 (1) 先求Big-O (即: 求Upper bound) Step 1: (按照遞迴式展開) 三個不同的遞迴呼叫次數 最頂層工作的執行次數 每一次遞迴呼叫時所會花費的成本

Step 2: (計算每一層之cost) n 7/8n 49/64n leaf Step 3: Total cost = n + 7/8n + 49/64n + … + leaf (公比小於1，用無窮等比級數求!!) ≤ n + 7/8n + 49/64n + … = n/(1-7/8) T(n) = O(n)

(1) + (2)  T(n) = (n) (2) 再求 (即: 求Lower bound) (Step 1與Step 2同前，故不再求) Step 3: Total cost = n + 7/8n + 49/64n + … + leaf  n T(n) = (n) (1) + (2)  T(n) = (n)

範例 2 若遞迴式T(n) = T(n/3) + T(2n/3) + n，試求T(n) = (?)。 (90, 91 台大類似題) Sol: (若要計算  得用“夾擠法”，分別計算O和) (1) 先求Big-O (即: 求Upper bound) Step 1: (按照遞迴式展開)

Step 2: (計算每一層之cost) n leaf = n < n

log3n 高度h’  高度h  分析 “高度h’ ” 分析 “高度h ” n → n/3 → n/9 → … → 1 h’ = log3n 高度 = log3n + 1 n → 2/3n → 4/9n → … → 1 n (2/3)h = 1, 0 ≤ h h = log3/2n 高度 = log3/2n + 1

(1) 先求Big-O (即: 求Upper bound) Step 3: Total cost = n + n + n + … + leaf (公比 r = 1，不能用無窮等比級數來賴皮) [解決方法]: 從 “高度” 下手 觀念: Total cost = n + n + n + … + leaf ≤ n + n + n + … + n (有log3/2n + 1個n) = n (log3/2n+1) T(n) = O(n log n) h’ h h (補滿)

(2) 再求 (即: 求Lower bound) Step 3: Total cost = n + n + n + … + leaf [解決方法]: 從 “高度” 下手 觀念: Total cost = n + n + n + … + leaf  n + n + n + … + n (有log3n + 1個n) = n (log3n+1) T(n) = (n log n) ∴ 根據 (1)+(2)，得知 T(n) = (n log n) (砍掉) h’ h’ h

範例練習 用遞迴樹法解T(n) = T(n/5) + T(7n/10) + n。 用遞迴樹法解T(n) = 3T(n/4) + cn2。

▓支配理論方法 (Master Theorem Method) 為附錄B.5的Theorem B.5 與Theorem B.6 的擴展。 當遞迴方程式具有某種特定型式時適用。 【精神】讓 f(n) 和 nlogba 比大小!!  是  的 General Case

範例 1 解 . T(n) = 8T(n/2) + n2 , . T(n) = 4T(n/2) + n2 Sol: . a = 8, b = 2, f(n) = n2  nlogba = nlog28 = n3 ∵n2 ≤ n3-0.5  f(n) = O(nlogba-ε) …  ∴T(n) = (nlogba) = (n3) . a = 4, b = 2, f(n) = n2  nlogba = nlog24 = n2 ∵n2 = n2  f(n) = (nlogba) …  ∴T(n) = (nlogbalg n) = (n2 lg n) ε= 0.5，ε可自設，只要大於0 且 不違反後續條件 即可!! 為何選用Big-O? ∵nlog28 = n3 明顯大於 f(n) = n2 Big-O 隱函有最大上限 (即 ≤) 之意 ∴選用Big-O表示 為何選用Theta? ∵nlog24 = n2 明顯等於 f(n) = n2 Theta隱函有相等 (即 =) 之意 ∴選用Theta表示

範例 2 解 . T(n) = 3T(n/2) + n2 , . T(n) = 4T(n/2) + n2 log n Sol: . a = 3, b = 2, f(n) = n2  nlogba = nlog23 = n1.5… ∵n2  n1.5… + 0.3  f(n) = (nlogba+ε) …  ∴T(n) = (f(n)) = (n2) . a = 4, b = 2, f(n) = n2 log n, k = 1  nlogba = nlog24 = n2  若 f(n) = (nlogba  lgkn), 則 T(n) = (nlogba  lgk+1n) …  ∴T(n) = (nlogbalgk+1n) = (n2 lg2n) 為何選用  ? ∵nlog23 = n1.5… 明顯小於 f(n) = n2  隱函有最小下限 (即 ) 之意 ∴選用  表示 為何選用Theta? ∵nlog24 = n2 明顯等於 n2，而且nlog24lg n = n2 lg n 也等於 f(n) = n2 log n Theta隱函有相等 (即 =) 之意 ∴選用Theta表示

課本附錄B之Example B.26, Example B.27, Example B.28 解 T(n) = 7T(n/2) + n3 範例練習 課本附錄B之Example B.26, Example B.27, Example B.28 解 T(n) = 7T(n/2) + n3 Ans: (n3) 解 T(n) = 3T(n/2) + n2log n Ans: (n2 lgn) (Hint: 本題不是以或來做判斷!!思考一下是以哪一個評判要件來決定的? 為什麼？) 解 T(n) = 4T(n/2) + n2/lg n, T(1) = c Ans: (n2 lg lg n) (Hint: 本題不能用支配定理，而是要用數學解法!!思考一下為什麼？)

補 充

補 1: 數學歸納法 (課本附錄A.3) 歸納法 (Induction) 是在當我們已經有一個可能的推論結果之後，用來驗証這個推論結果是否正確的工具。 它的步驟是： 驗証 n=1 時命題 f(n) 成立 (這叫歸納的基礎，或遞推的基礎) 假設 n=k 時命題f(n) 成立 (這叫歸納假設，或叫遞推的根據) 証明 n=k+1 於上述假設時，命題 f(n)成立。 為何需要數學歸納法 只通過有限多個實例並不足以証明一個命題是成立的。那麼要如何証明一個命題對所有自然數都正確呢？

數學歸納法外一章 (Copyright ©2001~2004昌爸工作坊 ) 數學歸納法是說：有一批編了號碼的數學命題，我們能夠證明第 1 號命題是正確的；如果我們能夠證明當第 n 號命題正確時，則第 n+1 號命題也是正確的，那麼整批命題都是正確的了。 這是由於能夠證明第n 號命題是正確，並不能保證第n+1 號命題也會是正確的。名數學家華羅庚講過一個故事： 「 一位買主買了一隻公雞回家。第一天，餵公雞一把米；第二天，又餵公雞一把米；第三天，還是餵公雞一把米。連續十天，每天都餵給公雞一把米。公雞就這十天的經驗，下了一個結論說：每天一定有一把米可吃。但是就在得出這個結論後不久，家裏來了一位客人，公雞就被宰殺成為盤中飧請客人了。」 華羅庚將這隻公雞如此得出結論的思考方法稱作公雞歸納法。而公雞歸納法是一種不完全歸納法。 華羅庚講這個故事的意思是說：「不能過分相信不完全歸納法。只對部分進行研究，得到一些結論，卻沒經過證明就說結論適用於全部，有時是要鬧出笑話的。」 在數學發展史上這樣的例子不少，例如，法國數學家Legendre A.M在1798年研究過二次函數f(n) = n2+n+41的值，當時他下了一個結論：它的函數值都是質數。而這個命題對不對呢？ 事實上，f(n) 經過計算，在n≤39時，得到的值確實都是質數。但是這個命題還是錯的，因為n = 40和41時， f(40) = 402+40+41 及 f(41) = 412+41+41 都不是質數。

歸納法的運作方式同骨牌效應 (Domino Principle) 假設我們透過函數 f(n) 排列出下圖的骨牌陣，其中骨牌間距比骨牌高度小，則: 我們可以推到第一張骨牌。 假設只要任意兩相鄰骨牌的距離都比骨牌的高度小，我們就可以保証只要第n個骨牌倒下，第n+1個骨牌就會被推倒。 第 1 張 第 n+1 張 假設函數 f(n) 是正確的!! ∵假設此函數正確，才有可能使任兩相鄰骨牌的距離比骨牌高度小 骨牌效應是以前後的結果來說明中間的未知情況 f(n)

若我們根據某一個問題的一些情況，推論出某個函數f(n)，可利用歸納法來証明此函數是否為該問題的解。 先証明當 n = 1 (或某一起始值) 時，這個推論結果 (即: f(n)) 是成立的 假設這個推論結果 f(n) 在n為任一正整數時是成立的，而當 n = n+1 (或某一起始值) 也是成立的話，那麼這個歸納就是成立的。 歸納法 (Induction) 的証明步驟: 找出歸納基底 (Induction base): 當 n=1 (或其它起始值)時，該推論結果為真的証明。 做歸納假設 (Induction hypothesis): 對任一 n1 (或其它起始值)，假設該推論結果為真。 找出歸納步驟 (Induction step): 當該推論結果對 n 為真，它對 n+1 也為真的証明。

試証對所有正整數n，下面的式子都成立: Sol: 找出歸納基底: 對於n=1, 做歸納假設: 假設對於任意正整數n，下列的式子成立: 找出歸納步驟: 我們必須証明 (  )

由於我們已証明n=1時成立，根據骨牌效應，如果歸納假設是成立的，那麼在n+1的情況下也一定是成立的。因此，對所有的正數n都是成立。 第3步的証明: 由於我們已証明n=1時成立，根據骨牌效應，如果歸納假設是成立的，那麼在n+1的情況下也一定是成立的。因此，對所有的正數n都是成立。 ( ) (  )

補 1 相關例題 Example A.2, Example A.3, Example A.4, Example A.5