來點不同的河內塔

河內塔？這不是入門級的演算法嗎？當然，這幾乎是每個程式人接觸遞迴時的必練之題，當初你是自行解出河內塔的嗎？如果不是的話，現在先別在網路搜尋解法，試著自行解解看，然後再來看看各種河內塔，你是否也解得出來呢？

雙色、三色河內塔

基本的河內塔，只有盤子大小之別，現在加點料，若有三種尺寸盤子，而每種尺寸的盤子有兩種顏色，例如藍與黃，現在於左柱上，依尺寸從下到上，依大藍、大黃、中藍、中黃、小藍、小黃堆疊，搬運盤子的目標，是讓黃色盤子全部位於中柱，而藍色盤子位於右柱，而且，搬運過程必須遵守大盤在小盤之下的規則，顏色順序則無限制。

如果你能自行解出單色河內塔，之後，面對雙色河內塔的第一個想法就是，先處理一種尺寸、兩色盤子時的狀況，這時，從左到中移動盤子，然後，從左到右移動另一盤，不過，接下來才是陷阱，你以為n種尺寸時，只要以n-1來遞迴呼叫同一函式，就可以解決問題，結果，卻會發生大盤開始凌駕於小盤之上的情況。

其實，真正要先解決的是，如何把左柱的盤子全部移到右柱。只有一種尺寸、兩色盤子時，移動順序是左至中、左至右、中至右（跟上頭相比，多了一次移動），而有n種尺寸時，只要以n-1及不同的來源、目標柱，遞迴呼叫同一函式，也就是解決n-1種尺寸移動後，移動最底層盤子，由於是雙色，遞迴與底盤處理會必須進行四次，才能將盤子全數移至右柱。

前面的過程會是一個函式，接下來，才是處理真正的雙色河內塔問題，這會是另一個函式。如果處理n種尺寸，那就用之前的函式，將n-1個盤子全部搬到右柱，將底盤從左柱搬至中柱，接著，將n-1個盤子又全部搬到中柱，將底盤從左柱搬至右柱，然後，將n-1個盤子全部搬到左柱，這時底盤處理完成，狀態就如同處理n-1種尺寸的雙色河內塔了，放心地呼叫目前的同一遞迴函式吧！

如果是三色河內塔呢？

同樣地，可以有一個函式，負責將左柱的盤子全部移到右柱，這時才能在另一個函式中，專心地處理最底層盤子的移動，雙色河內塔與三色河內塔非常適合用來體會遞迴威力，只要正確識別出同性質的子任務，告訴電腦子任務是什麼，剩下的處理細節就讓電腦去傷腦筋吧！（雙色與三色河內塔的實際程式碼，可參考https://goo.gl/l48wg5）

不遞迴的河內塔

如果我告訴你，遞迴是個很可愛的東西，你多半會不同意，遞迴只應天上有嘛！

但如果不覺得遞迴可愛，那多半是把自己當成電腦在想問題了，既然如此，那就當徹底一點，完全不使用遞迴來解河內塔如何？

先試著不使用遞迴來處理單色河內塔，如果是n個盤，可以直接把最上面的盤搬到右柱，就當成是最上層的盤處理完畢了嗎？

不行！因為這必然造成之後大盤凌駕於小盤之上。因此，你需要暫時將目前狀態放到一個袋子，並在上頭標號，然後變換目標柱，該動作必須持續到能把最下面的盤搬到目標柱為止，這時會有n-1有編號的袋子，從最後一個袋子中取出盤子狀態，將盤子移至目標柱，接下來，又得將盤子狀態放到另一個袋子裏了……

知道嗎？袋子就是在模擬電腦進行遞迴呼叫時，函式的狀態堆疊，如果函式中只遞迴呼叫自身一次，使用堆疊來模擬遞迴過程的話，基本上需要一個堆疊，單色河內塔遞迴解會在函式中，呼叫自身兩次，這需要兩個堆疊，把自己當成電腦來思考的話，就得小心堆疊中狀態的儲存與取出順序，才能正確地解決問題，無疑地，這是個繁瑣的過程（解題程式碼可參考https://goo.gl/buV8zZ）。

使用遞迴思考時的一個重要原則是，在子任務進行時，不該去思考父任務的狀態。

也就是，單看子任務本身時，每次都要是個全新任務，不會覺得有父任務的存在，這時，遞迴就會單純而可愛，如果實作遞迴時，開始感到複雜，那會是一個訊號，因為，你會不會是又開始在想著父任務狀態為何了呢？

那麼，有興趣挑戰非遞迴、使用堆疊模擬，來解出雙色或多色河內塔嗎？

如果想知道函式呼叫的堆疊是怎麼動作的話，儘管去試試看吧！不過，我完全不想挑戰，單色河內塔的堆疊模擬版本，已經足夠讓我知道電腦是怎麼處理函式堆疊了。

不堆疊的河內塔

當然，有些情況下，遞迴處理不是萬靈丹，通常相對來說，耗費的資源比較多，像是堆疊本身就需耗費記憶體，許多語言也會限制遞迴次數；有時為了效率，也必須試著找出其他方式來解題，或者試著記錄任務之間的狀態。例如，動態規畫演算時，為了避免子任務的重複計算，必須記錄子任務的最佳解，以便有效率地解決問題（記錄子任務狀態會比較適合，可以的話，儘量避免記錄父任務狀態，以免程式變得更複雜）。

以河內塔來說，存在不遞迴亦不使用堆疊模擬的解法，這來自於觀察遞迴版本的兩次遞迴呼叫間，會有一次將盤子從當次的左柱移至右柱的動作，這是一個節點，而前後兩次遞迴，會分別是個可展開的子樹，或者無法展開時，各是一個末端節點。簡單來說，將整個遞迴過程依此繪出，會是一棵二元樹，而搬運過程，就是走訪左樹、印出目前節點、走訪右樹的過程。

依上所述，若在每個節點記錄盤子編號、從幾號柱移至幾號柱，然後建出二元樹並走訪，就可獲得解答。

不過，談到二元樹的建立與走訪，使用遞迴來實作，還是比較方便的，若不想使用遞迴，程式實作的複雜度就又會加深了，有沒有辦法觀察到進一步的規律以簡化實作呢？

如果試著畫出二元樹並觀察走訪順序，當n為4時，移動的盤子編號順序，會是：1、2、1、3、1、2、1、4、1、2、1、3、1、2、1，數字左右對稱，感覺具有規律性，就結論而言，如果用二進位寫出這些數字，會發現相鄰數字間只有一個位元不同，這符合格雷碼（Gray code）的定義，只要能實作出產生這種格雷碼的產生（格雷碼不只一種），就能得到盤子的移動順序。

接著，我們觀察來源與目標柱。如果將柱子編號為1、2、3，並逆時針依序排列柱子，會發現如果某末端節點移動盤子時，是逆時針往下個柱子的話，該某層也都會是逆時針，而父節點該層，就都會是順時針往下個柱子，n個盤子就會有n層，n為偶數時，就是逆時針，奇數就是順時針。再接下來，就是將這些規律都實作出來了（可以參考https://goo.gl/bF4rDB）。

逐步觀察子任務

必須誠實地說，移動的盤子編號規律，讓我想破了頭，而它會是一種格雷碼，是從《名題精選百則/使用C語言》中得知的。因此，有時還是得從他人經驗中學習，對吧！

無論如何，程式的複雜性是增加了，不過因為子任務明確，相對於使用堆疊模擬的版本，還是很容易理解。這是因為，我們仍是基於有規則的遞迴版本，來進一步發掘出更細部的子任務，然而，如果是從電腦的角度來出發，那麼，大概很難察覺到這種可能性。

試著逐步觀察子任務，減少用電腦的角度來思考（儘管某些場合仍是必要的）。如果需要思考效率問題，可能性往往存在於已觀察到的規律中，就算最後某個子任務還是會用到遞迴，也沒關係，那也只是最後的實作形式罷了！