漢諾塔遞歸算法詳解：從問題分解到 C 語言實現

問題描述

有三根柱子 A、B、C，A 柱上從下到大疊放 n 個圓盤。目標：將所有圓盤移動到 C 柱，規則：一次只能移一個盤，大盤不能壓在小盤上。

遞歸思路

1. 基例：n = 1 時，直接將盤從源柱移到目標柱。
2. 遞歸步驟（n > 1）：
   1. 將最上方 n-1 個盤從源柱（A）借助目標柱（C）移到輔助柱（B）。
   2. 將第 n 個（最大）盤從源柱（A）移到目標柱（C）。
   3. 將 n-1 個盤從輔助柱（B）借助源柱（A）移到目標柱（C）。

C 語言完整實現

#include <stdio.h>

void move(char from, char to) {
    printf(\"%c --> %c\\n\", from, to);
}

void hanoi(int n, char source, char auxiliary, char target) {
    if (n == 1) {
        move(source, target);
    } else {
        hanoi(n - 1, source, target, auxiliary); // 步驟 1
        move(source, target);                    // 步驟 2
        hanoi(n - 1, auxiliary, source, target); // 步驟 3
    }
}

int main() {
    int n;
    printf(\"請輸入圓盤數量: \");
    scanf(\"%d\", &n);
    printf(\"移動步驟:\\n\");
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

複雜度分析

• 時間複雜度：O(2^n) — 移動次數為 2^n - 1。
• 空間複雜度：O(n) — 遞歸呼叫棧深度為 n。

常見誤區與修正

• 參數順序錯誤：遞歸呼叫時 source, auxiliary, target 位置必須對應邏輯角色，不能單純輪換。
• 忘記基例終止：缺少 if (n == 1) 會導致無限遞歸棧溢位。
• 移動計數器：若需統計步數，可在 move 中累加全域變數或回傳長整數。

延伸應用

漢諾塔模型廣泛應用於遞歸教學、編譯器優化（尾遞歸消除）、分散式系統資料遷移調度等領域。