在程式設計裡學「遞迴」時,河內塔幾乎一定會出現。用手解要走好幾百步,但寫成程式卻只要短短幾行。我們就依序來看看這其中的道理。柱子分成左、中間、右,圓盤依由小到大編為 1、2、3……號。

什麼是遞迴

遞迴,就是在解一個問題的步驟中,把同樣的步驟用在更小的問題上。一直縮小下去,總會碰到馬上就知道答案的問題(例如 0 個圓盤就什麼都不做),就在那裡停下來。

用遞迴思考河內塔

來想想把 n 個圓盤的塔從左邊移到右邊。

  1. 把上面的 n−1 個圓盤,從左邊移到中間。
  2. 把最大的圓盤 n,從左邊移到右邊。
  3. 把中間的 n−1 個圓盤,移到右邊。

1 和 3 都是「移動 n−1 個圓盤的塔」的問題,形式和原本的問題一樣。不同的只有從哪根柱子移到哪根柱子。所以只要做出一個「把 n 個圓盤從某根柱子,借助剩下的柱子,移到另一根柱子」的步驟,就可以在裡面呼叫它自己。

虛擬碼

步驟 hanoi(n, 來源柱, 目標柱, 輔助柱):
    如果 n 是 0,什麼都不做就結束
    hanoi(n − 1, 來源柱, 輔助柱, 目標柱)    … 搬開上面的 n−1 個
    把圓盤 n 從 來源柱 移到 目標柱
    hanoi(n − 1, 輔助柱, 目標柱, 來源柱)    … 把 n−1 個放回去

hanoi(3, 左, 右, 中間) 就會得出把 3 個圓盤從左邊移到右邊的步驟

光是這樣,不論幾個圓盤都能得出最少步數的走法。實際能執行的 Python 和 C 語言程式碼,介紹在用 Python、C 語言解河內塔。

呼叫的展開方式

3 個圓盤時,把 hanoi 是怎麼被呼叫的寫出來,就會變成下面這樣的樹狀。縮排越深,就是越內層的呼叫。

hanoi(3, 左→右)
├─ hanoi(2, 左→中間)
│   ├─ hanoi(1, 左→右)     … 1 移到右
│   ├─ 2 移到中間
│   └─ hanoi(1, 右→中間)   … 1 移到中間
├─ 3 移到右
└─ hanoi(2, 中間→右)
    ├─ hanoi(1, 中間→左)   … 1 移到左
    ├─ 2 移到右
    └─ hanoi(1, 左→右)     … 1 移到右

由上往下讀出來的「移動」順序,就是這 7 步的答案。一次呼叫會在內側產生兩次呼叫,所以每多一個圓盤,工作量就差不多變成 2 倍。

計算量

要查的項目n 個圓盤時
移動次數(步數)2ⁿ−1 次
呼叫 hanoi 的次數(0 個圓盤的呼叫也算)2ⁿ⁺¹−1 次
呼叫的深度(需要同時記住的量)n+1 層

步數是 2ⁿ−1 次的原因,在最少步數公式裡有證明。所需時間會隨圓盤個數呈指數成長(O(2ⁿ)),需要記住的量則只和個數成正比(O(n))。因為步數本身就有 2ⁿ−1 次,所以不論怎麼下工夫,要把全部步驟寫出來就是需要這麼多時間。

不用遞迴的解法

也有不用遞迴、只靠迴圈就能解的方法。這就是解法文章裡介紹過、用手解時的那套步驟。

步驟 hanoi_loop(n):
    決定 1 的方向(n 是奇數就依 左→右→中間,偶數就依 左→中間→右 的順序)
    對 步 = 1, 2, 3, … , 2ⁿ − 1 重複:
        如果 步 是奇數,就把圓盤 1 朝決定好的方向移到相鄰的柱子
        如果 步 是偶數,就比較沒放 1 的那兩根柱子最上面的圓盤,
                       把較小的移到較大的上面(或空柱子)

因為不需要像遞迴那樣記住呼叫,所以用到的記憶體非常少。

用二進位,直接求出任何一步

此外,還有一種不必追著前面的步驟走,就能直接求出第幾步該做什麼的方法。把柱子編成 0、1、2 號,對第 m 步(從 1 開始數):

  • 要移動的圓盤,是 m 寫成二進位時,結尾連續 0 的個數 + 1 號的圓盤。
  • 移動的來源柱,是 (m AND (m − 1)) 除以 3 的餘數。
  • 移動的目標柱,是 ((m OR (m − 1)) + 1) 除以 3 的餘數。

AND、OR 是二進位每一位數的「且」「或」運算。例如 m = 4(二進位是 100),結尾有 2 個 0,所以圓盤是 3 號;來源是 (4 AND 3) = 0,也就是 0 號柱;目標是 ((4 OR 3) + 1) = 8,8 除以 3 的餘數是 2,也就是 2 號柱。

用這個式子得出的步驟,圓盤是奇數個時是從 0 號柱移到 2 號柱,偶數個時是從 0 號柱移到 1 號柱。偶數個圓盤想移到 2 號柱時,把 1 號柱和 2 號柱對調來讀。步數和二進位之間這樣的關聯,在規律的文章裡有更詳細的介紹。