Chapter 6 遞迴
遞迴的基本觀念 遞迴：recursion，程式撰寫的重要技巧 特色： 函數以遞迴條件呼叫自己本身 必須加入終止條件，以免無窮的呼叫自己 增加可讀性，但是執行效率一般會比較差 某些程式語言沒有支援遞迴的程式撰寫
簡單的遞迴範例 sum(n) = [1 + 2 + 3 + … + (n-1)] + n //p6-4 = sum(n-1) + n int sum(int n) { int r; if (n==1) r = 1; else r = sum(n-1) + n; return (r); } sum(n) = [1 + 2 + 3 + … + (n-1)] + n = sum(n-1) + n 同樣的 sum(n-1) = sum(n-2) + n-1 … sum(n) = sum(n-1) + n = sum(n-2) + (n-1) + n = sum(n-3) + (n-2) + (n-1) + n = … stop condition : sum(1) = 1
遞迴設計 由上而下 top-down Divide And Conquer 原始問題可以切割成若干小問題 小問題與原始問題的“外觀”相同 小問題的資料量比原始問題縮小 Divide And Conquer 切割 分別處理 合併
遞迴呼叫的範例 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 //p6-7 void rec_prn(int n) { if (n>0) { rec_prn(n-1); printf("%d ", n); } 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 呼叫: rec_prn(4);
間接遞迴 函數呼叫自己本身，稱為直接遞迴 兩個以上函數互相呼叫，形成一迴路，稱為間接遞迴 例如：A呼叫B，B呼叫C，C呼叫A 思考停止條件時較為複雜
遞迴函數的思考 系統使用一個stack紀錄每次呼叫的順序 撰寫遞迴函數： trace遞迴函數： 找出遞迴條件 找出停止條件 由停止條件開始執行，找出執行的規則 將規則推廣至所有的情形
遞迴函數的例子 n!的計算 乘法的計算 a*b 河內塔問題(Tower of Hanoi) 最大公因數的計算
n!的計算 n! = 1 * 2 * 3 * ... * (n-1) * n 遞迴的條件 正式的條件 n! = n * (n-1)! 1! = 1 (這個理所當然的條件有什麼用？) 正式的條件 if n>1 if n=1
乘法的計算 a*b a * b 如何用加法的遞迴方式表示？ 遞迴條件：p6-32 a * b = a * (b-1) + a = [a * (b-2) + a] + a = ... 結束條件： a * 1 = a
練習 寫出n!的遞迴計算程式 程式可以執行，所以包含主程式 遞迴是自己呼叫自己，所以只需要一個函數 遞迴函數中，用if區分終止條件與遞迴條件 if n>1 if n=1 程式可以執行，所以包含主程式 遞迴是自己呼叫自己，所以只需要一個函數 遞迴函數中，用if區分終止條件與遞迴條件
河內塔問題(Tower of Hanoi) 問題：p6-12 搬移限制： 有三根柱子A、B、C 在A上面有n個盤子，由上而下編號1到n。考慮最簡單的情形 n=3 目標：將n個盤子搬到C 搬移限制： 每次只能搬移柱子最上面的一個盤子 在整個過程中，編號大的盤子不可以放在編號小的盤子上面
河內塔問題(Tower of Hanoi) A B C A B C
河內塔問題 - 3個盤子處理 將1號盤子從A搬到C 2號盤子從A搬到B 1號盤子自C搬到B 3號盤子搬到C 1號盤子從B搬到A
河內塔問題 - n個盤子處理 將1至n-1的盤子從A搬到B (借用C) 將編號n的盤子從A搬到C 把1至n-1的盤子從B搬到C 重點： 遞迴條件的停止？
河內塔問題 - n個盤子處理 A B C n 1 n-1 A B C n 1 n-1 A B C n 1 n-1 A B C n 1 n-1
河內塔問題-程式與時間複雜度 程式：p6-17 時間複雜度： 假設n個盤子搬移次數是h(n) n個盤子的搬移，等於兩次n-1盤子的搬移，加上一個單一盤子的移動 h(n) = 2 * h(n-1) + 1 用數學歸納法可證得，h(n) = 2n -1
最大公因數的計算 想一想，數學上最大公因數怎麼算？ e.g. gcd(180, 75) = 15 非遞迴的做法： 找出二者共同的質數因數，予以相乘
最大公因數的計算 gcd問題包含 一個終止條件(m<=n and n%m==0) 兩個遞迴條件 程式撰寫時，仍然是寫在一個函數內 if m<=n and n%m==0 if n<m otherwise gcd問題包含 一個終止條件(m<=n and n%m==0) 兩個遞迴條件 程式撰寫時，仍然是寫在一個函數內
其他常見的遞迴應用 Fibonacci費氏數列(費伯那西) if n = 1, 2 if n > 2 課本 p6-24