Java 遞迴 vs 迴圈效能比較與適用場景

結論

迴圈效能優於遞迴 (Java 無尾呼叫優化)。遞迴每層呼叫消耗堆疊幀，大量資料易導致 StackOverflowError。

效能對比 (簡易基準)

// 遞迴階乘
long factRec(int n) { return n <= 1 ? 1 : n * factRec(n - 1); }

// 迴圈階乘
long factIter(int n) { long r = 1; for (int i = 2; i <= n; i++) r *= i; return r; }

• n = 100,000：遞迴 → StackOverflowError；迴圈 → 瞬間完成 (結果溢位但不崩潰)。
• n = 10,000：遞迴約 2-3ms，迴圈約 0.1ms (JIT 優化後差距更大)。

適用場景

遞迴優化技巧

1. 尾遞迴手動轉迴圈：Java 編譯器不優化，需自行改寫。
2. 增加堆疊大小：-Xss2m (治標不治本)。
3. 使用 Trampoline / Continuation：函數式風格模擬尾呼叫 (較複雜)。
4. 迴圈 + 顯式堆疊：模擬遞迴過程 (如非遞迴 DFS)。

費波那契數列對比

// 遞迴 (指數複雜度 O(2^n)) - 極慢
long fibRec(int n) { return n <= 1 ? n : fibRec(n-1) + fibRec(n-2); }

// 迴圈 (線性 O(n)) - 快
long fibIter(int n) { 
    long a = 0, b = 1; 
    for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; } 
    return a; 
}

// 矩陣快速冪 / 公式法 (O(log n)) - 最快

**原則：能用迴圈解決的不用遞迴；天然遞迴結構 (樹/圖/分治) 用遞迴但注意深度。**