J2SE 遞歸算法入門 - 從階乘到斐波那契的經典實現

什麼是遞歸

遞歸是指函數在定義中直接或間接調用自身。解決問題時將大問題分解為結構相同的子問題，直到達到基本情況（基準情況）直接返回結果。

三大經典示例

1. 階乘計算

public static int factorial(int n) {
    if (n == 1) return 1; // 基準情況
    return n * factorial(n - 1); // 遞歸調用
}

執行流程：factorial(3) → 3 * factorial(2) → 3 * (2 * factorial(1)) → 3 * (2 * 1) = 6。

2. 1 到 n 求和

public static int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n - 1);
}

3. 十進制轉二進制

public static void toBinary(int n) {
    if (n == 0) return;
    toBinary(n / 2);
    System.out.print(n % 2); // 回溯時輸出，順序正確
}

4. 斐波那契數列

public static int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n-1) + fib(n-2);
}

注意：遞歸斐波那契時間複雜度 O(2^n)，極低效，實際應用應用動態規劃或矩陣快速冪。

遞歸 vs 迭代

遞歸設計三要素

1. 基準情況：終止條件，防止無限遞歸。
2. 遞歸步驟：問題規模縮小，向基準情況收斂。
3. 結果合併：子問題結果如何組合為當前問題結果。

常見陷阱

• 缺少基準情況導致棧溢出。
• 重複計算（如遞歸斐波那契），需備忘錄優化。
• 尾遞歸優化：Java 不支持，但可手動轉迭代。