Java 遞歸算法精講：階乘、斐波那契與實戰遞歸三要素

什麼是遞歸？

方法直接或間接調用自身的編程技巧。核心思想：將大問題分解為同性質的小問題，直到達到可直接解決的基本情況（基線條件）。

遞歸三要素（缺一不可）

1. 基線條件：停止遞歸的條件，防止無限遞歸導致 StackOverflowError
2. 遞歸推進：問題規模縮小，向基線條件逼近
3. 遞歸返回：從基線條件返回，逐層組合結果

經典例題一：階乘

數學定義

n! = n × (n-1)!，1! = 1

代碼實現

public static int factorial(int n) {
    if (n == 1) return 1;           // 基線條件
    return n * factorial(n - 1);    // 推進 + 返回
}

執行軌跡 (factorial(5))

factorial(5)
  5 * factorial(4)
    4 * factorial(3)
      3 * factorial(2)
        2 * factorial(1)  → 返回 1
        返回 2
      返回 6
    返回 24
  返回 120

經典例題二：斐波那契數列

定義

F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n>2)

遞歸實現

public static int fib(int n) {
    if (n == 1 || n == 2) return 1; // 基線條件
    return fib(n - 1) + fib(n - 2); // 推進 + 返回
}

性能陷阱

遞歸樹存在大量重複計算，時間複雜度 O(2^n)。fib(40) 已明顯卡頓，fib(50) 可能跑不出結果。

優化方案

1. 備忘錄（記憶化）：Map<Integer, Integer> memo 緩存結果，降為 O(n)
2. 動態規劃（自底向上）：迭代計算，O(n) 時間、O(1) 空間
3. 矩陣快速冪：O(log n)，適合極大 n

// 備忘錄版
private static Map<Integer, Integer> memo = new HashMap<>();
public static int fibMemo(int n) {
    if (n <= 2) return 1;
    if (memo.containsKey(n)) return memo.get(n);
    int res = fibMemo(n - 1) + fibMemo(n - 2);
    memo.put(n, res);
    return res;
}

實戰案例：目錄遍歷 / 文件搜索

public void listFiles(File dir) {
    File[] files = dir.listFiles();
    if (files == null) return; // 基線條件：空目錄或無權限
    for (File f : files) {
        if (f.isDirectory()) {
            listFiles(f); // 遞歸推進
        } else {
            System.out.println(f.getAbsolutePath()); // 處理文件
        }
    }
}

遞歸 vs 迭代

遞歸常見坑與調試技巧

1. 缺少基線條件 → StackOverflowError，必寫 if (baseCase) return
2. 推進方向錯誤 → 永遠不到基線，如 fib(n+1)
3. 重複計算 → 引入備忘錄或改 DP
4. 大對象傳遞 → 棧幀過大，改傳索引/引用
5. 調試技巧：IDE 設置「條件斷點」n == 3，觀察調用棧；或打印入參/出參追蹤流程

總結

遞歸是解決「自相似」問題的利器。掌握 基線條件、推進邏輯、返回組合 三要素，警惕 重複計算 與 棧溢出。實戰中：樹形結構首選遞歸，線性問題優先迭代，性能敏感處上備忘錄/DP。