C語言遞歸實現漢諾塔：經典算法完整解析與代碼示例

問題描述

漢諾塔（Tower of Hanoi）是經典遞歸問題：有三根柱子 A、B、C，A 柱上套著 n 個大小不一的圓盤（大在下、小在上）。目標是將所有圓盤移動到 C 柱，規則：每次只能移動一個圓盤，且大盤不能置於小盤之上。B 柱可作為輔助。

遞歸算法邏輯

將 n 個圓盤從 A 經 B 移至 C 的遞歸策略：

1. 基準情況：n = 1 時，直接將圓盤從 A 移至 C
2. 遞歸步驟（n > 1）：
   • 將 A 上的 n-1 個圓盤借助 C 移至 B
   • 將 A 上剩餘的第 n 個（最大）圓盤移至 C
   • 將 B 上的 n-1 個圓盤借助 A 移至 C

時間複雜度

移動次數遞推關係：T(n) = 2·T(n-1) + 1，解得 T(n) = 2^n - 1。時間複雜度為 O(2^n)，屬指數級增長。

C 語言完整實現

#include <stdio.h>

void move(int n, char from, char aux, char to);

int main() {
    char src = 'A', aux = 'B', dst = 'C';
    int n;
    printf("請輸入圓盤個數：");
    scanf("%d", &n);
    move(n, src, aux, dst);
    return 0;
}

// 將 n 個圓盤從 from 柱借助 aux 柱移動到 to 柱
void move(int n, char from, char aux, char to) {
    if (n == 1) {
        printf("圓盤編號 %d：從 %c 移動到 %c\n", n, from, to);
    } else {
        move(n - 1, from, to, aux);      // 步驟 1：n-1 從 from 經 to 移至 aux
        printf("圓盤編號 %d：從 %c 移動到 %c\n", n, from, to); // 步驟 2：最大盤 from → to
        move(n - 1, aux, from, to);      // 步驟 3：n-1 從 aux 經 from 移至 to
    }
}

執行示例（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 步（2^3 - 1），符合理論值。

關鍵點總結

• 遞歸函數參數順序體現「源、輔、目」角色在遞歸層級間的動態交換
• 基準情況處理最小問題單元，遞歸步驟分解大問題
• 輸出格式可擴展為記錄步驟序號、繪製動畫等
• 大 n 時遞歸深度較大，嵌入式環境需注意棧溢出風險

擴展思考

若需求變為「輸出總步數而非具體步驟」，可直接計算 (1 << n) - 1。若要非遞歸實現，可用棧模擬遞歸過程，或採用迭代算法（基於灰碼或二進制規律）。