漢諾塔問題 最簡單的圖文講解遞歸實作

問題簡化：

假設有 A,B,C三個柱子。有n個盤子，從大到小依次放在A柱上，我們目标是把A柱的盤子移到C柱。遵循如下原則:

1.小盤的上面不能放大圓盤。

2.在三根柱子之間一回隻能移動一個圓盤。

3.隻能移動在最頂端的圓盤。 

解法介紹

在了解遞歸時，難點就像國小生了解方程一樣，無法了解将未知的設定為x，假設它為已知的方式求解。遞歸也一樣，我們将某個函數通過定義，假設它能實作這個功能，并且在函數内部又肯定會依賴于這個功能，會發生自己調用自己的情況。比如我們這裡的功能機為：

tower(int n, string from, string to, string tmp)
這個功能機能實作将n個盤子，從源柱from，利用臨時柱tmp，最終将盤子移動到目标柱to上。
它既然能将n個盤子搬過去，那一定也能将n-1個盤子搬過去。這就是遞歸的精髓。遞歸的出口就是當隻有一個時，直接搬過去就行。      

思路與源碼：

這三個柱子在變換着充當源柱，目标柱，臨時柱。

void tower(int n, string from, string to, string tmp) {
    if (n == 1) {
        cout << n  << from << " to " << to << endl;   //A
    }
    else {
        tower(n - 1, from, tmp, to);  //B
        cout << n  << from << " to " << to << endl; //C
        tower(n - 1, tmp, to, from); //D
    }
}

int main(int argc, char** argv) {
    tower(7, " A ", " C ", " B ");
}