Java 遞歸經典範例：階乘與費波那契數列完整解析

Java 遞歸經典範例：階乘與費波那契數列完整解析

遞歸是程式設計中解決「問題可分解為相同子問題」的強大技術。本文透過兩個經典範例——階乘計算與費波那契數列——詳細拆解遞歸的三要素：終止條件、遞歸規律、回溯邏輯。

範例一：求階乘 (Factorial)

數學定義

n! = n × (n-1) × ... × 1，其中 1! = 1 (終止條件)。

遞歸拆解

• 終止條件：if (n == 1) return 1;
• 遞歸規律：n * factorial(n-1)

完整代碼

public class FactorialDemo {
    public static int factorial(int n) {
        if (n == 1) {          // 終止條件
            return 1;
        }
        return n * factorial(n - 1);  // 遞歸規律
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));  // 輸出 120
    }
}

執行軌跡 (以 5! 為例)

factorial(5)
→ 5 * factorial(4)
  → 4 * factorial(3)
    → 3 * factorial(2)
      → 2 * factorial(1)
        → 1 (命中終止條件，開始回溯)
      → 2 * 1 = 2
    → 3 * 2 = 6
  → 4 * 6 = 24
→ 5 * 24 = 120

範例二：費波那契數列 (Fibonacci)

數學定義

F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n≥3)。

遞歸拆解

• 終止條件：if (n==1 || n==2) return 1;
• 遞歸規律：fib(n-1) + fib(n-2)

完整代碼

public class FibonacciDemo {
    public static int fib(int n) {
        if (n == 1 || n == 2) {  // 終止條件
            return 1;
        }
        return fib(n - 1) + fib(n - 2);  // 遞歸規律
    }

    public static void main(String[] args) {
        System.out.println("第 9 項: " + fib(9));  // 輸出 34
    }
}

效能陷阱與優化方向

費波那契遞歸存在大量重複計算 (時間複雜度 O(2^n))。例如 fib(5) 會重複計算 fib(3)、fib(2) 多次。

優化策略

1. 記憶化 (Memoization)：用 Map<Integer, Integer> 快取已計算結果，降至 O(n)。
2. 動態規劃 (迭代)：自底向上迭代，空間 O(1)。
3. 矩陣快速冪 / 公式法：O(log n) 級別，適用極大 n。

記憶化版本示例

public class FibonacciOptimized {
    private static Map<Integer, Integer> cache = new HashMap<>();

    public static int fib(int n) {
        if (n == 1 || n == 2) return 1;
        if (cache.containsKey(n)) return cache.get(n);
        int result = fib(n - 1) + fib(n - 2);
        cache.put(n, result);
        return result;
    }
}

遞歸設計檢查清單

• ☐ 是否有明確的終止條件 (避免 StackOverflowError)？
• ☐ 每次遞歸呼叫是否縮小問題規模 並向終止條件收斂？
• ☐ 子問題是否重疊？若是，考慮記憶化或 DP。
• ☐ 遞歸深度是否超過 JVM 棧限制？深度大時改用迭代或尾遞歸優化 (Java 不原生支援尾呼叫優化)。

總結

遞歸代碼簡潔優雅，但需警惕效能與棧溢位風險。階乘屬於線性遞歸 (單路徑)，費波那契屬於樹狀遞歸 (多路徑、重疊子問題) —— 理解兩者差異是掌握遞歸優化的關鍵。