Java 遞歸核心原理圖解：從階乘到費波那契的思維建模

遞歸是「用有限代碼描述無限過程」的強大技術。很多初學者陷入「無限循環」恐懼，實則遞歸只有三個核心要素：**邊界條件、遞推前進、遞推返回**。本文通過兩個經典案例，幫你建立清晰的遞歸心智模型。

遞歸三要素模板

返回類型 方法(參數) {
    if (邊界條件) return 基礎值;           // 1. 邊界：停止遞歸
    // 2. 遞推前進：縮小問題規模，調用自身
    // 3. 遞推返回：組合子問題結果
    return 組合(方法(縮小後參數), ...);
}

案例一：階乘 n!

數學定義：n! = n × (n-1)!，0! = 1

public static long factorial(int n) {
    if (n <= 1) return 1;              // 邊界：n=0 或 1
    return n * factorial(n - 1);       // 遞推：n * (n-1)!
}

調用棧視覺化（n=5）：

factorial(5)
  5 * factorial(4)
    4 * factorial(3)
      3 * factorial(2)
        2 * factorial(1)
          return 1          ← 邊界返回
        return 2 * 1 = 2
      return 3 * 2 = 6
    return 4 * 6 = 24
  return 5 * 24 = 120

案例二：費波那契數列 F(n)

定義：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n≥3)

public static long fibonacci(int n) {
    if (n <= 2) return 1;              // 邊界：前兩項
    return fibonacci(n - 1) + fibonacci(n - 2); // 遞推：兩子問題合併
}

遞歸樹呈指數級增長，大量重複計算（F(3) 被算多次），時間複雜度 O(2ⁿ)。

優化路徑

遞歸 vs 迭代：選型指南

• **結構遞歸**（樹、圖、分治）：遞歸代碼更直觀，優先選擇
• **線性遞歸**（階乘、費波、尾遞歸）：迭代效能更好，無棧溢出風險
• **尾遞歸優化**：JVM 目前不支援 TCO，手動改寫為迭代

實戰陷阱與對策

1. StackOverflowError：深度過大 → 改迭代或增加 -Xss
2. 重複計算：加 @Cacheable / 手動備忘錄
3. 參數未縮小：邏輯錯誤導致無限遞歸 → 單元測試覆蓋邊界
4. 不可變對象累積：字串拼接產生大量臨時對象 → 用 StringBuilder

總結

遞歸本質是「問題分解 + 邊界收斂」。掌握「寫出邊界 → 寫出遞推關係 → 驗證參數單調縮小」三步法，配合備忘錄/動規優化工具箱，即可駕馭絕大多數遞歸場景。記住：能用迭代解決的，盡量不用遞歸。