Java 算法實現：為什麼應盡量避免遞歸，改用迭代？

現象：遞歸雖優雅，但性能是隱患

遞歸在算法描述、代碼結構理解上很直觀，但在 Java 實現時往往不是最優選。實測同等邏輯，非遞歸實現速度可提升 30%~50%，甚至更高。

實測對比：計算 Σlog(i) (i=1..N)

// 遞歸實現
public static double recursive(long n) {
    if (n == 1) return Math.log(1);
    return Math.log(n) + recursive(n - 1);
}

// 迭代實現
public static double directly(long n) {
    double result = 0;
    for (int i = 1; i <= n; i++) {
        result += Math.log(i);
    }
    return result;
}

測試結果 (N=5,000,000，-Xss200m)

recursive result: 7.212475098340103E7
recursive time used: 539,457,109 ns  // ~539 ms
non-recursive result: 7.212475098340103E7
non-recursive time used: 282,479,757 ns  // ~282 ms

遞歸耗時接近迭代的 2 倍。若棧空間不足（默認 -Xss1m），遞歸直接拋 StackOverflowError。

根本原因：Java 線程棧幀開銷

每次方法調用涉及：

1. 為新方法分配棧幀
2. 保存當前方法棧幀狀態
3. 上下文切換到新棧幀

遞歸導致大量棧幀創建/切換，消耗棧內存與 CPU 時間。迭代僅在單棧幀內循環，無此開銷。

最佳實踐原則

• 理解算法用遞歸，實現算法用迭代：幾乎所有遞歸算法都可轉換為迭代（显式棧模擬）
• 尾遞歸優化：Java 編譯器/JVM 不支持 尾調用優化（TCO），不要指望編譯器自動優化
• 必要時調大棧：-Xss 參數，但治標不治本
• 複雜遞歸（如樹遍歷）可用顯式 Stack 數據結構模擬

迭代版樹遍歷示例

// 前序遍歷非遞歸
public void preorder(TreeNode root) {
    if (root == null) return;
    Stack stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        visit(node);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

結語

遞歸是思維工具，迭代是工程工具。追求高性能、高穩定性的 Java 系統中，將遞歸轉為迭代是基礎優化原則。