「今天不寫扣（Code）」

但為什麼？
其實個人一直覺得理解河內塔的情況分兩種：

1. 一點就通
2. 十點沒通

還是那句：為什麼？

因為遞迴本身其實就有點抽象了，套用到河內塔上，而沒有玩過河內塔（或是玩不起來），就會超級抽象。而河內塔的程式個人覺得不會太難，主要是「理解」要怎麼寫出來的邏輯比較困難，所以今天會專注在講邏輯上。

當然能不能講解得清楚也的確讓自己很擔心就是……大挑戰捏

認識河內塔

河內塔規則基本上是這樣：

1. 有三根柱子，其中一根柱子上套了n個中間有洞的圓盤（下面叫他甜甜圈吧！）
2. 甜甜圈上至下依序由小到大
3. 大的甜甜圈不可以放在小的甜甜圈之上
4. 一次只能拿一個甜甜圈，放下後才可以拿另一個
5. 目標是把所有甜甜圈搬到另一根柱子上

所以理論上不會出現上面這種情況

解析河內塔

下面我們用原柱、其他柱、目標柱來代稱這三根柱子

• 原柱：原本放甜甜圈的柱子
• 目標柱：甜甜圈要移過去的柱子
• 其他柱：暫時放甜甜圈用的柱子，因為他不是原柱也不是目標柱

接著我們一一從最底層開始吧！

n=1

我們先假設n=1（1個甜甜圈）的情況，這個情況下，原柱的甜甜圈只有1個，沒有任何阻礙，我們就直接把它拿到目標柱就解決了。

夠直覺吧？那這個就是遞迴中的終止條件了，因為它完全不用做其他事，直接拿過去就好了。

n=2

好，問題來了，我們要把2個甜甜圈從原柱搬到目標柱，但我們不能直接把大的甜甜圈拿起來放到目標柱，這時該怎麼辦？

依照河內塔的規則，我們應該要先把上面那個甜甜圈暫時拿到其他柱，接著就能把大甜甜圈拿去目標柱了對吧？接著再把暫時放到其他柱的甜甜圈放到大甜甜圈上

順序就是：

1. 把上面的小甜甜圈拿到其他柱
2. 把下面的大甜甜圈拿到目標柱
3. 把其他柱上的小甜甜圈拿到目標柱

嗯～聽起來好像很合理，好像就是把上面的甜甜圈暫時移走，把下面的甜甜圈拿到目標，再把原本的甜甜圈拿到目標去對吧？

讓我們再往下看一個例子

n=3

我們從最下面開始看吧，甜甜圈有大、中、小，如果要搬大甜甜圈到目標柱怎麼辦？
是不是要先把上面的中、小甜甜圈先搬到其他柱，再把大甜甜圈移到目標柱，對吧？
而中、小甜甜圈不能暫時放在目標柱上，不然大甜甜圈無法移動到目標柱上（聽起來是廢話，但記得要想到這點）

所以理論上要先像上面這樣，把大甜甜圈上面的東西搬到其他柱對吧？

好，我們問題往下走，暫時不看大甜甜圈，要怎麼把中、小甜甜圈搬到其他柱？

好像……有點眼熟诶？那不就是n=2的情況嗎？只是目標柱在中間而已！

所以n=3會包含n=2的情況，而n=2搬動甜甜圈其實也包含n=1的情況，這邊就有遞迴的邏輯了！

所以說：

1. n=1直接搬，上面沒甜甜圈（終止條件）
2. n=2之中要做n=1的情況，只是柱子順序不同
3. n=3之中要做n=2的情況，只是柱子順序不同
4. 以此類推

程式邏輯

用pseudo code來簡單帶一下吧：

我們應該要有個搬河內塔的方法，他應該要收這些東西：

搬河內塔(層數, 原柱, 目標柱, 其他柱);

會長這樣子

搬河內塔(層數, A, B, C){
    if(層數==1){
        搬甜甜圈(A, B);
    } else {
        搬河內塔(層數-1, A, C, B);
        // 暫時把上面的東西搬到其他柱的C
        搬甜甜圈(A, B);
        // 把大甜甜圈搬到目標柱的B
        搬河內塔(層數-1, C, B, A);
        // 注意：因為東西先暫時搬到C，所以要把C上的東西搬到B
    }
}

然後他應該要照上面的邏輯進行

還是不懂怎麼辦？

個人建議是找一個河內塔的遊戲，照著我們上面的範例，一步一步走，慢慢去了解這個概念。

當然上面並不是最完整、有效率的pseudo code，只是示範起見。但了解概念之後，實際去實作就相對沒那麼困難了。