Java 遞歸解決漢諾塔問題：完整邏輯、圖解與效能分析

漢諾塔是經典遞歸教學案例。本文提供標準遞歸實作、移動步驟數學推導、非遞歸迭代版本、可視化輸出與時間複雜度分析，幫助徹底理解遞歸思維。

問題定義

• 三根柱子：A (起始)、B (輔助)、C (目標)。
• N 個盤子，小盤在上、大盤在下。
• 規則：一次移一盤、大盤不可壓小盤。
• 目標：將所有盤子從 A 移至 C。

遞歸核心邏輯

將 N 個盤子從 from 移至 to (借助 inter)：

1. 將頂部 N-1 個盤子從 from 移至 inter (借助 to)。
2. 將第 N 個盤子 (最大) 從 from 移至 to。
3. 將 N-1 個盤子從 inter 移至 to (借助 from)。

基礎情況：N=1 時直接移動。

標準遞歸實作

public class HanoiTower {

    public static void move(int n, char from, char inter, char to) {
        if (n == 1) {
            System.out.printf("移動盤子 %d: %c -> %c%n", n, from, to);
            return;
        }
        move(n - 1, from, to, inter);   // 步驟 1
        System.out.printf("移動盤子 %d: %c -> %c%n", n, from, to); // 步驟 2
        move(n - 1, inter, from, to);   // 步驟 3
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println("=== 漢諾塔 " + n + " 階移動步驟 ===");
        move(n, 'A', 'B', 'C');
        System.out.println("總步數: " + ((1 << n) - 1)); // 2^n - 1
    }
}

輸出示例 (N=3)

=== 漢諾塔 3 階移動步驟 ===
移動盤子 1: A -> C
移動盤子 2: A -> B
移動盤子 1: C -> B
移動盤子 3: A -> C
移動盤子 1: B -> A
移動盤子 2: B -> C
移動盤子 1: A -> C
總步數: 7

數學推導：最少移動次數

設 T(n) 為 n 階最少步數。

T(1) = 1

T(n) = T(n-1) + 1 + T(n-1) = 2*T(n-1) + 1

解得：T(n) = 2^n - 1

非遞歸迭代實現 (棧模擬)

public static void moveIterative(int n, char from, char inter, char to) {
    // 任務幀：{n, from, inter, to, stage}
    // stage=0: 執行前遞歸; stage=1: 移動當前盤; stage=2: 執行後遞歸
    record Frame(int n, char from, char inter, char to, int stage) {}

    Deque stack = new ArrayDeque<>();
    stack.push(new Frame(n, from, inter, to, 0));

    while (!stack.isEmpty()) {
        Frame f = stack.pop();
        if (f.n == 1) {
            System.out.printf("移動盤子 1: %c -> %c%n", f.from, f.to);
            continue;
        }
        switch (f.stage) {
            case 0:
                // 逆序壓棧：後遞歸 -> 移動 -> 前遞歸
                stack.push(new Frame(f.n, f.from, f.inter, f.to, 2));
                stack.push(new Frame(1, f.from, f.inter, f.to, 0)); // 移動當前盤
                stack.push(new Frame(f.n - 1, f.from, f.to, f.inter, 0));
                break;
            case 2:
                stack.push(new Frame(f.n - 1, f.inter, f.from, f.to, 0));
                break;
        }
    }
}

遞歸深度與棧溢出風險

• Java 預設棧大小 -Xss1m，約支援 10,000~20,000 遞歸深度 (視幀大小)。
• 漢諾塔遞歸深度 = N，N > 10,000 會 StackOverflowError。
• 實際上 N=30 步數已達 10 億，執行時間才是瓶頸，非棧深度。

進階：記錄移動軌跡供可視化

record Move(int disk, char from, char to) {}

public static List solve(int n) {
    List moves = new ArrayList<>();
    move(n, 'A', 'B', 'C', moves);
    return moves;
}

private static void move(int n, char from, char inter, char to, List moves) {
    if (n == 1) {
        moves.add(new Move(1, from, to));
        return;
    }
    move(n - 1, from, to, inter, moves);
    moves.add(new Move(n, from, to));
    move(n - 1, inter, from, to, moves);
}

此列表可直接餵給 JavaFX/Swing/前端進行動畫渲染。

教學重點總結

1. 分解子問題：N 階 = (N-1) 階 + 1 步 + (N-1) 階。
2. 參數角色互換：遞歸呼叫時 from/inter/to 位置輪換，理解「借助誰」的含義。
3. 基礎情況：N=1 直接處理，避免無限遞歸。
4. 時間複雜度：O(2^N) 指數級，僅適合教學/小 N。