class1introduction第一課導論.pptVIP

計算機與工程問題解析導論 第十課 遞迴 遞迴 遞迴是一種劃分-克服(或劃分-組合)的解題方法： method Recurse(Arguments) if (SmallEnough(Arguments)) // 終止 return Answer else // 劃分 Identity=Combine( SomeFunc(Arguments), Recurse(SmallerArguments)) return Identity // 組合 若你能將問題寫成由更小問題的組合，那你就能在Java中用它來做為遞迴演算法了。 找出陣列中的最大值 假定吾人同時只能找出兩個數的最大值，假設吾人要在一組8個數字中找出最大值。 35 74 32 92 53 28 50 62 吾人的最大值方法的自我遞迴呼叫： 最大公因數 給定兩個非負整數且 ab，則a和b的最大公因數為： b%a 和 a 的最大公因數直到 a==0 則為b 範例 範例 呼叫順序 總結 遞迴方法是直接或間接呼叫自己(實際上大部份是直接呼叫) 。 遞迴是基於區分與克服： 將原來的問題減少成一連串更小的實例，直到小到可以直接解答 然後組合子問題的解答來建構原有問題解答 遞迴是一群非程序性語言工作的觀點 Java是程序性的：你必須告訴電腦要做什麼以及怎麼做(像C++, Visual Basic,…也是) 非程序性語言：你告訴電腦要做什麼然後它會想出如何去做(Prolog) gcd(12,18) = gcd(18%12,12) gcd(6,12) = gcd(12%6,6) gcd(0,6) 6 import javax.swing.*; // 支援簡單的輸入 public class GCD { public static void main(String[] args) { String input= JOptionPane.showInputDialog(Enter a); int a= Integer.parseInt(input); input= JOptionPane.showInputDialog(Enter b); int b= Integer.parseInt(input); System.out.println(gcd is + gcd(a,b)); } public static int gcd(int a, int b) { if(a == 0) return b; else return gcd(b%a,a); } }