Java 實現漢諾塔：遞歸、非遞歸模擬與規律解法完整代碼解析

漢諾塔（Hanoi Tower），又稱河內塔，是一個源自印度古老傳說的經典益智遊戲，也是計算機科學中展示遞歸算法威力的經典案例。本文將深入解析三種不同的 Java 實現方式：標準遞歸解法、使用棧模擬遞歸的非遞歸解法，以及基於漢諾塔移動規律的非遞歸解法，並提供完整可運行的代碼示例。

問題背景與規則

根據傳說，大梵天創造世界時做了三根金剛石柱子，在一根柱子上從下往上按大小順序疊著 64 片黃金圓盤。婆羅門需將圓盤從一根柱子移至另一根，規則如下：

• 一次只能移動一個圓盤
• 小圓盤上不能放大圓盤
• 三根柱子之間移動

對於 n 個圓盤，最少需要移動 2^n - 1 步才能完成。

解法一：遞歸實現

遞歸是解決漢諾塔最直觀的方法。核心思想是將 n 個盤子的移動分解為：

1. 將 n-1 個盤子從起始柱移至輔助柱
2. 將第 n 個盤子從起始柱移至目標柱
3. 將 n-1 個盤子從輔助柱移至目標柱

public void play_recursive(int num, char A, char B, char C) {
    if (num == 1) {
        System.out.println(A + " -> " + C);
        return;
    } else {
        play_recursive(num - 1, A, C, B);
        System.out.println(A + " -> " + C);
        play_recursive(num - 1, B, A, C);
    }
}

遞歸解法代碼簡潔、邏輯清晰，但存在函數調用開銷大、棧溢出風險等問題，不適合超大數據量場景。

解法二：非遞歸實現——模擬遞歸思維

利用棧數據結構手動模擬遞歸調用過程。每個棧元素封裝了一個「任務」，包含盤子數量、起始/輔助/目標柱標識，以及狀態標記（status）。

class Disk {
    char A, B, C;
    int status; // status=1 表示可直接移動
    
    public Disk(int status, char A, char B, char C) {
        this.status = status;
        this.A = A; this.B = B; this.C = C;
    }
}

public void play_non_recursive(int diskNum) {
    Stack stack = new Stack();
    stack.push(new Disk(diskNum, 'A', 'B', 'C'));
    Disk popDisk = null;
    
    while ((popDisk = stack.pop()) != null) {
        if (popDisk.status == 1) {
            System.out.println(popDisk.A + " -> " + popDisk.C);
        } else {
            // 逆序壓棧，模擬遞歸調用順序
            stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A, popDisk.C));
            stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));
            stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C, popDisk.B));
        }
    }
}

關鍵點：將遞歸的三步操作逆序壓入棧中，利用 status 標記區分「需分解」與「可直接執行」的任務，完美模擬遞歸調用棧。

解法三：非遞歸實現——基於移動規律

漢諾塔存在明確的移動規律，可直接推導每一步操作，無需遞歸或棧模擬：

• 將三柱排列成三角形：盤數為偶數時按 A→B→C 順時針，奇數時按 A→C→B 順時針
• 最小盤每次按三角形方向移動到下一根柱子
• 其他兩根柱子之間進行唯一合法移動（小盤疊大盤、或空柱接收盤子）
• 交替執行上述兩步，共 2^n - 1 步完成

public void play_regular(int diskNum) {
    Stack_play_regular A = new Stack_play_regular('A');
    Stack_play_regular B = new Stack_play_regular('B');
    Stack_play_regular C = new Stack_play_regular('C');
    
    for (int i = diskNum; i > 0; i--) A.push(i);
    
    Stack_play_regular[] towers = new Stack_play_regular[3];
    towers[0] = A;
    if (diskNum % 2 == 0) { towers[1] = B; towers[2] = C; }
    else { towers[1] = C; towers[2] = B; }
    
    int towerOfMinimunDisk = 0;
    int totalMoves = (int) (Math.pow(2, diskNum) - 1);
    
    for (int i = 0; i < totalMoves; ) {
        // 移動最小盤
        Stack_play_regular tower = towers[towerOfMinimunDisk];
        Stack_play_regular nextTower = towers[(towerOfMinimunDisk + 1) % 3];
        System.out.println(tower.name + " -> " + nextTower.name);
        nextTower.push(tower.pop());
        i++;
        towerOfMinimunDisk = (towerOfMinimunDisk + 1) % 3;
        
        // 移動其他兩柱之間的合法盤子
        Stack_play_regular t1 = towers[(towerOfMinimunDisk + 1) % 3];
        Stack_play_regular t2 = towers[(towerOfMinimunDisk + 2) % 3];
        
        if (canMove(t2, t1)) {
            System.out.println(t2.name + " -> " + t1.name);
            t1.push(t2.pop());
            i++;
        } else if (canMove(t1, t2)) {
            System.out.println(t1.name + " -> " + t2.name);
            t2.push(t1.pop());
            i++;
        }
    }
}

private boolean canMove(Stack_play_regular from, Stack_play_regular to) {
    return (from.getTop() != -1) && 
           (to.getTop() == -1 || from.showTopDisk() < to.showTopDisk());
}

此解法時間複雜度 O(2^n)，空間複雜度 O(n)，無遞歸開銷，適合大規模盤子數量。

輔助類：棧實現

代碼中使用了兩種棧：

• Stack：存儲 Disk 任務對象，用於模擬遞歸
• Stack_play_regular：存儲盤子 ID (int)，用於規律解法模擬三柱狀態

兩者均基於數組實現，提供 push、pop、getTop、showTopDisk 等核心操作。

總結與建議

學習漢諾塔不僅是掌握一個經典算法，更是理解遞歸與迭代轉換、數學規律在算法設計中應用的絕佳案例。建議初學者先從遞歸入手理解核心邏輯，再嘗試實現非遞歸版本以鍛煉數據結構運用能力。