第2章中文(ppt).ppt

Chapter 2 Recursion: The Mirrors Recursive Solutions (遞迴求解) 遞迴是很有效的解決問題技巧 將問題分解成幾個較小(指引數的值會越來越接近基本狀況)的相同問題 是使用迴圈的列舉法 (iteration) 的替代方案 循序搜尋是一種列舉求解法 由資料集的最前面開始 依序檢視資料集的每一個項目 Recursive Solutions 二位元搜尋是一種遞迴解法 重覆將資料集減半，並決定前半或後半會包含搜尋的項目 這使用了切割再征服 (divide and conquer) 策略 Recursive Solutions 遞迴函式的幾個現象 遞迴函式會呼叫自己 每次遞迴呼叫解決一個相同但是較小的問題 測試到基本狀況時就不再遞迴呼叫 基本狀況: 在遞迴定義中已知答案的情形 問題會越來越小，最後較小的問題會達到基本狀況 Recursive Solutions 建置遞迴函式的 4 個問題 如何將問題以相同之較小問題定義? 每一遞迴呼叫如何縮小問題? Recursive Solutions 建置遞迴函式的 4 個問題(Continued) 那些狀況可以作為基本狀況? 隨著問題越來越小, 是否一定會達到基本狀況? 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 A Recursive Valued Method: The Factorial of n factorial(n) 的遞迴定義 factorial(n) = 1 if n = 0 = n * factorial(n-1) if n 0 A Recursive Valued Method: The Factorial of n 遞迴關係 一個新項目的值是利用之前項目的值來產生的數學公式 Example factorial(n) = n * [(n-1) * (n-2) * … * 1] = n * factorial(n-1) A Recursive Valued Method: The Factorial of n 用方盒追蹤答案 (Box trace) 一種系統化的追蹤遞迴函式的動作的方法 每一方盒對應到一個啟動紀錄 (activation record) 包含了一個函式在遞迴呼叫時及遞迴呼叫結果的區域環境 範例 A Recursive Valued Method: The Factorial of n A Recursive Valued Method: The Factorial of n A Recursive Valued Method: The Factorial of n A Recursive Valued Method: The Factorial of n A Recursive Valued Method: The Factorial of n A Recursive Valued Method: The Factorial of n 一個函式的區域環境包括: 此函式的區域變數 (local variables) 各引數的值的複製 此函式結束後要回到 呼叫它的函式 的位置 ( return address, 是一記憶體地址 ) 函式自己本身的內容 兔子的繁殖 (費式序列)(The Fibonacci Sequence) “Facts” about rabbits 兔子永遠不會死掉 每隻兔子都在出生 2 個月後成熟(可以開始繁殖), 也就是在出生後第 3 個月的開頭開始繁殖 每個月的開頭每對成熟的公兔及母兔會生下一對公兔及母兔 Multiplying Rabbits (The Fibonacci Sequence) Problem 在第 n 個月共有幾對兔子? 遞迴關係 rabbit(n) = rabbit(n-1) + rabbit(n-2) Multiplying Rabbits (The Fibonacci Sequence) Multiplying Rabbits (The Fibonacci Sequence) 基本狀況 rabbit(2), rabbit(1) 遞迴定義 rabbit(n) = 1 if n is 1 or 2