漢諾塔遞歸算法：從文字邏輯到代碼實現的理解路徑

為何難理解？

漢諾塔是**遞歸思維**的經典入門，**代碼極短但抽象度高**，初學者常試圖「展開每一步」導致腦內棧溢出。

文字邏輯（不看代碼先懂這個）

將 N 個盤子從 A 柱借助 B 柱移到 C 柱：

1. 先將上面 N-1 個盤子從 A **借助 C** 移到 B。
2. 再將第 N 個（最大）盤子從 A 直接移到 C。
3. 最後將 N-1 個盤子從 B **借助 A** 移到 C。

**遞歸終止條件**：N=1 時直接移動。

代碼對應關係

void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to); // 步驟 2
        return;
    }
    hanoi(n-1, from, to, aux);   // 步驟 1：參數順序變化體現「借助」角色互換
    printf("Move disk %d from %c to %c\n", n, from, to); // 步驟 2
    hanoi(n-1, aux, from, to);   // 步驟 3
}

理解技巧：信任遞歸、不展開

• **假設 `hanoi(n-1, ...)` 已經能正確完成子任務**（數學歸納法思想）。
• 只關注**當前層**的三步：移上層、移底盤、移上層。
• 參數 `from/aux/to` 的語義**隨遞歸層級動態變化**，這是難點也是精髓。

可視化輔助

在線動畫演示：Math is Fun - Tower of Hanoi，可調盤數、步進執行，觀察遞歸調用棧與移動序列對應關係。

複雜度

• 移動次數：2^N - 1（指數級）。
• 時間/空間複雜度：O(2^N) / O(N) 遞歸棧深度。

**掌握漢諾塔，就是掌握了「分治 + 遞歸 + 參數語義翻轉」的核心模式，可遷移至二叉樹遍歷、DFS、分治排序等眾多問題。**