漢諾塔遞歸算法思維解析：從問題分解到邊界條件的數學歸納法本質

為什麼人類難以直觀想出遞歸解

人類工作記憶有限（約 7±2 塊），遞歸嵌套超過 3-4 層即難以心理模擬，類似《盜夢空間》深層夢境。

計算機遞歸執行模型

• 調用棧自動管理狀態：每層調用保存局部變量、返回地址
• 無「思維負擔」：機械執行展開與回溯
• 關鍵在於程序員正確定義：遞歸關係 + 基線條件

漢諾塔遞歸推導過程

1. 目標：將 n 個盤子從 A 經 B 移至 C
2. 分解：
  ① 將 n-1 個盤子從 A 經 C 移至 B (子問題)
  ② 將第 n 個盤子從 A 移至 C (基線操作)
  ③ 將 n-1 個盤子從 B 經 A 移至 C (子問題) 3. 基線條件：n=1 時直接移動 4. 數學歸納法證明：假設 n-1 可解 → n 可解 → 所有 n 可解

代碼模板

void hanoi(int n, char from, char aux, char to) {
    if (n == 1) { move(from, to); return; }
    hanoi(n-1, from, to, aux);   // ①
    move(from, to);              // ②
    hanoi(n-1, aux, from, to);   // ③
}

學習建議

• 先寫 n=1,2,3 完整移動序列，觀察模式
• 畫遞歸樹：根節點 n，左右子樹 n-1
• 理解「問題規模遞減」+「合併子問題結果」通用範式
• 練習：斐波那契、二叉樹遍歷、快速排序、全排列

遞歸不是「人腦模擬」，而是「定義規則讓機器執行」。掌握「寫出正確遞歸關係與基線」比「心理跑通遞歸」重要百倍。