您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 遞歸計算階乘：5! 遞歸實現與棧幀分析

編輯：Java 相關知識

遞歸定義

n! = n × (n-1)!   (n > 1)
1! = 1
0! = 1

原始代碼

import java.util.Scanner;

public class FactorialRecursive {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        FactorialRecursive fr = new FactorialRecursive();
        System.out.println(fr.recursion(n));
    }
    
    public long recursion(int n) {
        long value = 0;
        if (n == 1 || n == 0) {
            value = 1;           // 基線條件
        } else if (n > 1) {
            value = n * recursion(n - 1);  // 遞歸步驟
        }
        return value;
    }
}

棧幀演示 (計算 5!)

recursion(5)
  5 * recursion(4)
    4 * recursion(3)
      3 * recursion(2)
        2 * recursion(1)
          return 1
        return 2 * 1 = 2
      return 3 * 2 = 6
    return 4 * 6 = 24
  return 5 * 24 = 120

遞歸三要素

尾遞歸優化嘗試 (Java 不支援)


// 尾遞歸形式：遞歸調用是最後操作
long factTail(int n, long acc) {
    if (n <= 1) return acc;
    return factTail(n - 1, n * acc);  // 最後一步是遞歸調用
}

// 調用: factTail(5, 1)
// Java 編譯器/JVM 不會優化為迭代，仍會產生 n 層棧幀
// Scala/Kotlin/Scala 支援 @tailrec 編譯器優化

迭代版 (生產首選)

long factIterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

BigInteger 版 (無溢出)

BigInteger factBig(int n) {
    BigInteger result = BigInteger.ONE;
    for (int i = 2; i <= n; i++)
        result = result.multiply(BigInteger.valueOf(i));
    return result;
}

輸入驗證增強

public long safeRecursion(int n) {
    if (n < 0) throw new IllegalArgumentException("負數無階乘");
    if (n > 20) throw new IllegalArgumentException("超過 long 範圍，請用 BigInteger");
    return recursion(n);
}