Java 遞歸算法計算階乘：經典入門範例與堆疊溢位風險分析

遞歸是演算法設計的核心思想之一。計算階乘 n! 是遞歸最經典的教學案例。本文提供標準遞歸實作、迭代對比、尾遞歸優化（Java 不支援 TCO）與 **堆疊溢位風險分析**，幫助初學者建立正確的遞歸思維。

標準遞歸實作

public class FactorialRecursive {
    public static long factorial(int n) {
        if (n < 0) throw new IllegalArgumentException("n 不可為負數");
        if (n <= 1) return 1;          // 基礎情況
        return n * factorial(n - 1);   // 遞歸步驟
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("請輸入非負整數: ");
        int n = sc.nextInt();
        System.out.println(n + "! = " + factorial(n));
    }
}

執行流程圖解（以 4! 為例）

factorial(4)
    → 4 * factorial(3)
        → 3 * factorial(2)
            → 2 * factorial(1)
                → 1 (基礎情況返回)
            → 2 * 1 = 2
        → 3 * 2 = 6
    → 4 * 6 = 24

迭代寫法對比（推薦生產使用）

public static long factorialIterative(int n) {
    if (n < 0) throw new IllegalArgumentException("n 不可為負數");
    long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

尾遞歸優化嘗試（Java 不支援 TCO）

// 尾遞歸形式：遞歸呼叫為最後一步運算
public static long factorialTailRec(int n, long acc) {
    if (n <= 1) return acc;
    return factorialTailRec(n - 1, n * acc);
}
// 呼叫：factorialTailRec(5, 1)

雖寫成尾遞歸，**Java 編譯器/JVM 不執行尾調用優化 (TCO)**，仍會產生 O(n) 堆疊幀。Scala、Kotlin (編譯器插件)、C++ (優化開啟) 支援 TCO。

大數階乘：BigInteger 突破 long 極限

import java.math.BigInteger;

public static BigInteger factorialBig(int n) {
    BigInteger result = BigInteger.ONE;
    for (int i = 2; i <= n; i++) result = result.multiply(BigInteger.valueOf(i));
    return result;
}
// 100! = 933262154439... (158 位數)

遞歸三要素檢核表

1. 基礎情況： 條件明確、必達、無邊界疏漏（如 n <= 1）。
2. 遞歸步驟： 規模嚴格遞減，向基礎情況收斂。
3. 組合結果： 正確組合子問題解得原問題解。

常見遞歸陷阱

• 缺少基礎情況 → 無限遞歸 → StackOverflowError。
• 遞減邏輯錯誤（如 n-2 導致奇偶不全覆蓋）。
• 重複計算子問題（如費波納契遞歸），需加備忘錄或改動態規劃。

理解遞歸本質與限制，是演算法進階的關鍵門檻。