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

Java 遞歸算法實作：階乘計算完整範例

編輯：Java 相關知識

遞歸是程式設計中極具威力的技巧，它允許方法直接或間接呼叫自身來解決問題。本文透過一個經典的 Java 範例——計算階乘，詳細示範如何實作簡單的遞歸演算法。

程式碼架構解析

範例程式主要包含兩個類別：DiGui 作為主程式進入點，負責處理使用者輸入與輸出；Child 類別則封裝了遞歸邏輯。以下是完整的原始碼：

// CFAN 2002
// 遞歸演算法
// 求階乘
import java.io.*;

public class DiGui {
    public static void main(String args[]) {
        int i = 0;
        char ch = ' ';
        String s;
        Child ren = new Child();
        try {
            System.out.println("Please input a Number, End with '#'");
            do {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                s = br.readLine();
                i = Integer.parseInt(s);
                System.out.println(ren.Factorial(i));
            } while (ch != '#');
        } catch (IOException e) {}
    }
}

class Child {
    double Factorial(int n) {
        if (n == 1)
            return 1;
        else
            return n * Factorial(n - 1);
    }
}

核心邏輯深度剖析

遞歸終止條件

if (n == 1) return 1; 是遞歸的基準情況。當輸入值遞減至 1 時，停止遞歸呼叫並返回 1，防止無限遞歸導致堆疊溢位。

遞歸呼叫與回溯

return n * Factorial(n - 1); 將問題分解為「當前數值 × (n-1) 的階乘」。每次呼叫都會在堆疊中保留當前狀態，直到觸發終止條件，隨後層層回溯計算最終結果。

程式執行流程

主程式建立 Child 物件並進入迴圈等待使用者輸入
讀取整數後呼叫 Factorial() 方法
遞歸方法逐層分解問題直到 n=1
結果經由回溯機制逐層相乘並返回
主程式輸出計算結果

潛在問題與改進建議

輸入驗證缺失：原始碼未檢查負數或零輸入，會導致無限遞歸。建議加入 if (n <= 1) return 1;
迴圈終止邏輯錯誤：變數 ch 永遠為空格，無法透過 '#' 結束迴圈。應改為檢查輸入字串 s
資料型別限制：double 回傳型別雖能處理較大數值，但會失去精度。大數運算建議使用 BigInteger
資源管理：BufferedReader 應在 finally 區塊或 try-with-resources 中關閉

改良版範例

import java.io.*;
import java.math.BigInteger;

public class FactorialCalculator {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            System.out.println("請輸入非負整數 (輸入 'q' 結束)：");
            String input;
            while ((input = br.readLine()) != null) {
                if ("q".equalsIgnoreCase(input)) break;
                try {
                    int n = Integer.parseInt(input.trim());
                    if (n < 0) {
                        System.out.println("請輸入非負整數！");
                        continue;
                    }
                    System.out.println(n + "! = " + factorial(BigInteger.valueOf(n)));
                } catch (NumberFormatException e) {
                    System.out.println("輸入格式錯誤，請重新輸入！");
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static BigInteger factorial(BigInteger n) {
        return n.equals(BigInteger.ZERO) || n.equals(BigInteger.ONE) 
            ? BigInteger.ONE 
            : n.multiply(factorial(n.subtract(BigInteger.ONE)));
    }
}

遞歸與迭代的效能考量

雖然遞歸程式碼優雅簡潔，但每次呼叫都消耗堆疊空間。對於階乘這類線性遞歸，迭代寫法效能更佳且無堆疊溢位風險：

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