遞迴 Recursion
遞迴的基本觀念 遞迴：recursion，程式撰寫的重要技巧 特色： 函數以遞迴條件呼叫自己本身 必須加入終止條件，以免無窮的呼叫自己 增加可讀性，但是執行效率一般會比較差 某些程式語言沒有支援遞迴的程式撰寫 支援：C、VB
直接遞迴與間接遞迴 系統使用一個stack紀錄每次呼叫的順序 函數呼叫自己本身，稱為直接遞迴 兩個以上函數互相呼叫，形成一迴路，稱為間接遞迴 例如：A呼叫B，B呼叫C，C呼叫A
簡單的遞迴範例 //計算1+2+…+n sum(n) = [1 + 2 + 3 + … + (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
如何追蹤遞迴結果 DEMO…
什麼時候可以使用遞迴解決問題 當你的問題具有遞迴特性的時候 花時間去分析問題
如何設計遞迴 找出遞迴規則 設定終止條件 避免造成無窮遞迴
遞迴函數的例子 n!的計算 乘法的計算 a*b 最大公因數的計算 河內塔問題(Tower of Hanoi)
n!的計算 n! = 1 * 2 * 3 * ... * (n-1) * n 遞迴的規則 終止條件 n! = n * (n-1)! 1! = 1 終止條件 n=1時終止 if n>1 if n=1
練習 寫出n!的遞迴計算程式 程式主程式main() 直接遞迴，所以只需要一個遞迴函數fac() 遞迴函數中，用if區分終止條件與遞迴條件 if n>1 if n=1 程式主程式main() 直接遞迴，所以只需要一個遞迴函數fac() 遞迴函數中，用if區分終止條件與遞迴條件
乘法的計算 a*b a * b 如何用加法的遞迴方式表示？ 遞迴條件： a * b = a * (b-1) + a = [a * (b-2) + a] + a = ... 結束條件： a * 1 = a
河內塔問題(Tower of Hanoi) 問題： 搬移限制： 有三根柱子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
河內塔問題-程式與時間複雜度 時間複雜度： 假設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) 兩個遞迴條件 程式撰寫時，仍然是寫在一個函數內
問題 1+2+3+…+N 想出各種解法？
作業一 Fibonacci費氏數列(費伯那西) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … if n = 1, 2 if n > 2