Java 遞歸詳解：以九九乘法表為例深入剖析

前言

遞歸是程式設計中極具威力卻也容易讓初學者困惑的概念。本文將透過經典的「九九乘法表」範例，由淺入深說明 Java 中遞歸的運作機制、堆疊幀變化，並與迴圈寫法比較記憶體效能，幫助你徹底掌握遞歸精髓。

一、迴圈版九九乘法表（基礎寫法）

最直觀的實作方式是使用雙層 for 迴圈：

package test.ms;

public class Test99 {
    public static void main(String[] args) {
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= i; j++) {
                System.out.print(j + " * " + i + " = " + (i * j) + " ");
            }
            System.out.println();
        }
    }
}

此寫法邏輯清晰、效能極佳，是大多數開發者的首選。

二、遞歸版九九乘法表（核心示範）

若要用遞歸實現相同功能，關鍵在於「將問題分解為子問題」：

package test.ms;

public class MultiTable {
    public static void main(String[] args) {
        m(9); // 從第 9 行開始遞歸
    }

    /**
     * 遞歸列印九九乘法表
     * @param i 目前要列印的行號 (1~9)
     */
    public static void m(int i) {
        if (i == 1) { // 基礎案例：第 1 行直接列印
            System.out.println("1*1=1 ");
        } else {
            m(i - 1); // 先處理前 i-1 行（遞歸呼叫）
            // 當前行列印邏輯
            for (int j = 1; j <= i; j++) {
                System.out.print(j + "*" + i + "=" + (j * i) + " ");
            }
            System.out.println();
        }
    }
}

三、遞歸執行流程圖解：堆疊幀的推疊與彈出

理解遞歸的關鍵在於掌握 方法堆疊（Call Stack） 的動態變化：

1. 推疊階段：main 呼叫 m(9) → m(9) 呼叫 m(8) → … → m(2) 呼叫 m(1)。每一次呼叫都會產生一個新的堆疊幀，壓入堆疊頂端。此時 i 從 9 遞減至 1，j 尚未開始執行。
2. 基礎案例執行：m(1) 符合 i == 1，直接列印 1*1=1，方法結束返回。
3. 彈出階段（回溯）：m(1) 彈出，m(2) 繼續執行其 for 迴圈（j=1..2）列印第 2 行 → m(2) 彈出 → m(3) 列印第 3 行 … 依此類推，直到 m(9) 列印完第 9 行並彈出，程式結束。

關鍵觀察：i 在每一層堆疊幀中都是獨立的區域變數，遞減於推疊階段；j 則是在各自幀彈出時才從 1 遞增至 i。正是這種「先深入到底，再層層回溯執行後續邏輯」的特性，構成了遞歸獨特的執行順序。

四、遞歸 vs 迴圈：記憶體與效能比較

結論：遞歸雖優雅，但會消耗額外棧空間，深度過大易導致 StackOverflowError。九九乘法表屬於簡單迭代問題，生產環境強烈建議使用迴圈；遞歸版本僅供教學示範與理解堆疊機制。

五、總結與最佳實踐

• 遞歸三要素：基礎案例、遞歸規則、狀態變化（讓問題規模縮小）。
• 除非問題天然適合遞歸（如檔案目錄遍歷、二叉樹操作），否則優先考慮迴圈。
• 若必須用遞歸且深度不可控，可考慮尾遞歸優化（Java 編譯器不直接支援，需手動轉迴圈）或增加 -Xss 擴大棧大小。
• 善用除錯工具觀察 Call Stack 變化，是掌握遞歸最快的途徑。

希望本文能幫你建立清晰的遞歸心智模型，歡迎在留言區交流心得！