Recursion: The Mirrors Chapter 2 Recursion: The Mirrors

Recursive Solutions (遞迴求解) 遞迴是很有效的解決問題技巧 將問題分解成幾個較小(指引數的值會越來越接近基本狀況)的相同問題 是使用迴圈的列舉法 (iteration) 的替代方案 循序搜尋是一種列舉求解法 由資料集的最前面開始 依序檢視資料集的每一個項目 © 2005 Pearson Addison-Wesley. All rights reserved

Recursive Solutions 二位元搜尋是一種遞迴解法 重覆將資料集減半，並決定前半或後半會包含搜尋的項目 這使用了切割再征服 (divide and conquer) 策略 © 2005 Pearson Addison-Wesley. All rights reserved

Recursive Solutions 遞迴函式的幾個現象 遞迴函式會呼叫自己 每次遞迴呼叫解決一個相同但是較小的問題 測試到基本狀況時就不再遞迴呼叫 基本狀況: 在遞迴定義中已知答案的情形 問題會越來越小，最後較小的問題會達到基本狀況 © 2005 Pearson Addison-Wesley. All rights reserved

Recursive Solutions 建置遞迴函式的 4 個問題 如何將問題以相同之較小問題定義? 每一遞迴呼叫如何縮小問題? © 2005 Pearson Addison-Wesley. All rights reserved

Recursive Solutions 建置遞迴函式的 4 個問題(Continued) 那些狀況可以作為基本狀況? 隨著問題越來越小, 是否一定會達到基本狀況? © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: n ! (n 階乘) Problem 計算出 n! (以函式 factorial(n) 表示) factorial(n) 的列舉式定義(可用迴圈完成，請自己寫寫看) factorial(n) = n * (n-1) * (n-2) * … * 1 for any integer n > 0 factorial(0) = 1 © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n factorial(n) 的遞迴定義 factorial(n) = 1 if n = 0 = n * factorial(n-1) if n > 0 © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n 遞迴關係 一個新項目的值是利用之前項目的值來產生的數學公式 Example factorial(n) = n * [(n-1) * (n-2) * … * 1] = n * factorial(n-1) © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n 用方盒追蹤答案 (Box trace) 一種系統化的追蹤遞迴函式的動作的方法 每一方盒對應到一個啟動紀錄 (activation record) 包含了一個函式在遞迴呼叫時及遞迴呼叫結果的區域環境 © 2005 Pearson Addison-Wesley. All rights reserved

範例 © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n Figure 2.3 A box © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n © 2005 Pearson Addison-Wesley. All rights reserved

A Recursive Valued Method: The Factorial of n 一個函式的區域環境包括: 此函式的區域變數 (local variables) 各引數的值的複製 此函式結束後要回到 呼叫它的函式 的位置 ( return address, 是一記憶體地址 ) 函式自己本身的內容 © 2005 Pearson Addison-Wesley. All rights reserved

兔子的繁殖 (費式序列) (The Fibonacci Sequence) “Facts” about rabbits 兔子永遠不會死掉 每隻兔子都在出生 2 個月後成熟(可以開始繁殖), 也就是在出生後第 3 個月的開頭開始繁殖 每個月的開頭每對成熟的公兔及母兔會生下一對公兔及母兔 © 2005 Pearson Addison-Wesley. All rights reserved

Multiplying Rabbits (The Fibonacci Sequence) Problem 在第 n 個月共有幾對兔子? 遞迴關係 rabbit(n) = rabbit(n-1) + rabbit(n-2) © 2005 Pearson Addison-Wesley. All rights reserved

Multiplying Rabbits (The Fibonacci Sequence) Figure 2.10 Recursive solution to the rabbit problem © 2005 Pearson Addison-Wesley. All rights reserved

Multiplying Rabbits (The Fibonacci Sequence) © 2005 Pearson Addison-Wesley. All rights reserved

Multiplying Rabbits (The Fibonacci Sequence) 基本狀況 rabbit(2), rabbit(1) 遞迴定義 rabbit(n) = 1 if n is 1 or 2 = rabbit(n-1) + rabbit(n-2) if n > 2 費氏序列 以 rabbit(1), rabbit(2), rabbit(3), … 這些值形成的序列 © 2005 Pearson Addison-Wesley. All rights reserved

Mr. Spock’s 兩難問題 (自 n 個物件取出 k 個的可能組合個數) Problem 在太陽系中要自 n 個星球中選擇 k 個星球來加以探索的可能組合個數? © 2005 Pearson Addison-Wesley. All rights reserved

Mr. Spock’s Dilemma (Choosing k out of n Things) 以 c(n, k) 表示自 n 個星球中選擇 k 個星球的可能組合個數 以星球 X 來看: c(n, k) = X 含在 k 個星球的可能組合個數 + X 不含在 k 個星球的可能組合個數 © 2005 Pearson Addison-Wesley. All rights reserved

Mr. Spock’s Dilemma (Choosing k out of n Things) 自 n 個物件取出 k 個的可能組合個數是以下兩數之和 自 n-1 個物件取出 k-1 個的可能組合個數 及自 n-1 個物件取出 k 個的可能組合個數 c(n, k) = c(n-1, k-1) + c(n-1, k) © 2005 Pearson Addison-Wesley. All rights reserved

Mr. Spock’s Dilemma (Choosing k out of n Things) 基本狀況 自 k 個物件取出 k 個只有一種取法 c(k, k) = 1 什麼都不取的取法也只有一種 c(n, 0) = 1 無法取出比 n 更多個物件 c(n, k) = 0 if k > n © 2005 Pearson Addison-Wesley. All rights reserved

Mr. Spock’s Dilemma (Choosing k out of n Things) 遞迴定義 c(n, k) = 1 if k = 0 1 if k = n 0 if k > n c(n-1, k-1) + c(n-1, k) if 0 < k < n © 2005 Pearson Addison-Wesley. All rights reserved

Mr. Spock’s Dilemma (Choosing k out of n Things) Figure 2.12 The recursive calls that c(4, 2) generates © 2005 Pearson Addison-Wesley. All rights reserved

Searching an Array: 找到陣列最大值 遞迴解法 if (anArray 只有一個項目) { maxArray(anArray) 就是該項目 } else if (anArray 有不只一個項目) { maxArray(anArray) 是以下兩數之最大值： maxArray( anArray 的前面一半陣列) 及 maxArray( anArray 的後面一半陣列) } // end if © 2005 Pearson Addison-Wesley. All rights reserved

Searching an Array: Finding the Largest Item in an Array Figure 2.13 Recursive solution to the largest-item problem © 2005 Pearson Addison-Wesley. All rights reserved

找到陣列中第 k 個最小值 遞迴解法: 由陣列中選擇一個樞紐項目 將陣列的項目重組, 或切割, 成比此樞紐項目小及比此樞紐項目大的陣列(排序) 將此策略遞迴用於其中的一個切割 © 2005 Pearson Addison-Wesley. All rights reserved

Finding the kth Smallest Item in an Array Figure 2.18 A partition about a pivot © 2005 Pearson Addison-Wesley. All rights reserved

Finding the kth Smallest Item in an Array Let: kSmall(k, anArray, first, last) = anArray[first..last] 中第 k 個最小項目 © 2005 Pearson Addison-Wesley. All rights reserved

Finding the kth Smallest Item in an Array 解答(假設陣列已排序): kSmall(k, anArray, first, last) = kSmall(k,anArray,first,pivotIndex-1) if k < pivotIndex – first + 1 = p if k = pivotIndex – first + 1 = kSmall(k-(pivotIndex-first+1), anArray, pivotIndex+1, last) if k > pivotIndex – first + 1 © 2005 Pearson Addison-Wesley. All rights reserved

Organizing Data: The Towers of Hanoi (河內塔) Figure 2.19a and b a) The initial state; b) move n - 1 disks from A to C © 2005 Pearson Addison-Wesley. All rights reserved

The Towers of Hanoi Figure 2.19c and d c) move one disk from A to B; d) move n - 1 disks from C to B © 2005 Pearson Addison-Wesley. All rights reserved

The Towers of Hanoi 擬程式碼 solveTowers(count,source,destination,spare) if (count is 1) { 直接將盤子由 source 移至 destination } else { solveTowers(count-1, source, spare, destination) solveTowers(1, source, destination, spare) solveTowers(count-1, spare, destination, source) } //end if © 2005 Pearson Addison-Wesley. All rights reserved

Recursion and Efficiency(效率) 有些遞迴解法非常慢，以致於不應該被採用 造成遞迴解法非常慢的原因 遞迴呼叫的花費時間 某些遞迴演算法內在就是無效率 © 2005 Pearson Addison-Wesley. All rights reserved

Recursion and Efficiency 如果某遞迴演算法無效率，又存在一個清楚而有效率的列舉解法，那就不要採用該遞迴演算法 如課本 p. 101 頁計算費氏序列的列舉演算法就是清楚而有效率的列舉解法 © 2005 Pearson Addison-Wesley. All rights reserved

Summary Recursion solves a problem by solving a smaller problem of the same type Four questions: How can you define the problem in terms of a smaller problem of the same type? How does each recursive call diminish the size of the problem? What instance of the problem can serve as the base case? As the problem size diminishes, will you reach this base case? © 2005 Pearson Addison-Wesley. All rights reserved

Summary A recursive call’s postcondition can be assumed to be true if its precondition is true The box trace can be used to trace the actions of a recursive method Recursion can be used to solve problems whose iterative solutions are difficult to conceptualize © 2005 Pearson Addison-Wesley. All rights reserved

Summary Some recursive solutions are much less efficient than a corresponding iterative solution due to their inherently inefficient algorithms and the overhead of method calls If you can easily, clearly, and efficiently solve a problem by using iteration, you should do so © 2005 Pearson Addison-Wesley. All rights reserved