問題說明

現在想像有一個盤子上有3根木樁，最左邊的木樁上有n個由小到大堆疊的盤子，現在要將這些盤子照著原來樣子搬移到最右邊的木樁，可是有以下3個條件 :

1. 盤子可以移動到任一木樁。
2. 每根木樁上的盤子，大盤一定要放在小盤下。
3. 一次只能移動一個盤子，且要從最上面的開始移動。
   
   (圖片來源 : Wikipedia)
   這就是很經典的「河內塔」問題。原則來說，河內塔能被擺在任一根木樁上，但為了我們程式好完成以及好解釋，所以統一將塔放在最左邊，需要移動到最右邊。

範例程式

先說結論，移動n個盤子需要2^n - 1次。

在此範例中，將盤子的數量設定為 3，因為在解釋上會比大的河內塔好理解，只是相同概念使用。
→ 木樁我們用A,B,C代表，盤子由上到下則是1,2,3

public class Hanoi {
        static void hanoitower(int n,char a,char b,char c){
            if(n==1){
                System.out.println("移動盤"+n+": " +"從" + a +"到"+ c);
            }
            else{
                hanoitower(n-1,a,c,b);
                System.out.println("移動盤"+n+": " +"從" + a +"到"+ c);
                hanoitower(n-1,b,a,c);
            }
        }
        public static void main(String[] args) {
            int plantNum = 3;
            hanoitower(plantNum,'A','B','C');
        }
}

• 河內塔使用到大量的遞迴結構，所以先行規劃好演算法(algorithm)就顯得特別重要。
  我們對此程式的解法應該是 :

1. 盤1,2移到B柱(各別處理)
2. 盤3移到C柱
3. 盤1移到A柱
4. 盤2,1移到C柱(各別處理)
   

• 程式解析:

Step 1 : 我們傳入一共有3個盤子的河內塔。遞迴的部分會一直出現在else裡面，當最後n = 1時，即表示將盤子1移到C柱，接著會return回去原呼叫的地方(第7行)，接著第二個盤子移動到B柱(第8行)，第9行由hanoi(2,A,C,B)當作引數傳入，最後第一個盤子由C移到B。

Step 2 : 此時因為我們一開始的第三個盤子還沒有return回去，回到第8行印出。接著由此開始，不斷從第9行遞迴，直到最後回傳值為空值(void)，函數結束。

線上工具與教學

因為此部分比較難懂，以下分享兩個工具幫助大家理解!!!

C++程式設計 [11.2]河內塔01版程式解析

(影片來源)
這部影片是我當初自學河內塔時，認為說明的很清楚的一支影片!!!(語法部分可忽略，僅聽解析)

Python Tutor : Visualize code in Python,JavaScript,C,C++,and Java

這是一個線上的視覺化工具， 支援不同程式語言。可以將上面提供的範例程式複製到此，可以在旁邊的空間一步一步了解河內塔是如何進行遞迴的。

以上內容若有錯誤，煩請不吝嗇告知!!!謝謝您!!!!