理論程式設計——簡單的一些遞迴例子
雖然上兩篇的說明中有階乘，Fibonacci 函式，這樣這麼好的例子來解釋遞迴程式執行的例子，但是這樣就會給你留下一個遞迴只能在數學的函式領域上使用的印象，但是事實上，只要事件滿足遞迴的兩個條件，都可以用遞迴來解決。這篇文章就來介紹一下遞迴在非數學領域的應用。
Palindromes問題
palindromes，迴文數，就是一個字串無論從前面開始讀，還是後面開始讀，他們的讀取結果一樣，例如：
level、noon。
觀察一個單詞是否是迴文數，通常的做法是，對比第一跟最後一個數是不是相同，對比第二跟倒數第二個數是不是相同。直到對比的是中間那個數。於是我們可以這樣實現：
bool
isPalindrome
（
string
str
）
{
int
n
=
str
。
length
（）；
for
（
int
i
=
0
；
i
<
n
/
2
；
i
++
）
{
if
（
str
［
i
］
！=
str
［
n
-
i
-
1
］）
return
false
；
}
return
true
；
}
這樣我們需要關注足夠多的細節。n是奇數的時候會不會算出小數啊，他的匹配過程是怎麼樣子的啊。
其實我們現在換個角度看，它是否為迴文數。我們只需要觀察到的就是，在一個非單個字母的迴文數中，它的裡面一定包含更短的迴文數，舉個例子，“level”，這個迴文數中，裡面有更小的迴文數“eve”。因此當我們要檢測一個數是否是迴文數的時候，你需要做的是：
什麼情況下它一定是迴文數，不再需要驗證（
找simple case
）。
否則我們就重複這樣做：
對比第一個字母跟最後一個字母是不是相等
第一個字母跟最後一個字母裡面的內容是不是迴文數
於是後面兩個很好實現，現在我們回答上述的第一個問題，我們看，level中的v，到了它之後就沒有人跟它匹配了，因為這個單詞的字母數量是奇數，除了他之外它兩邊都是對稱的，從左往右或者從往左讀都不影響迴文數的結構，因此到了它我們無需繼續判斷。第二，觀察noon，他們是完全匹配，對稱軸是oo中間的空字元，也就是說當字元自己為的時候，也無需匹配，因為意味著匹配完了。
所以我們得出：
if（str。length（） <2）{
return true；
}
在對應分解部分：
對比第一個字母跟最後一個字母是不是相等：
if（str［0］ == str［str。length（） - 1］
第一個字母跟最後一個字母裡面的內容是不是迴文數：
isPalindrom（str。substr（1， len -2）
於是我們可以得到這樣的實現程式碼：
bool isPalindrom（string str） {
int len = str。length（）；
if（str。length（） < 2） {
return true；
}else {
return str［0］ == str［len - 1］ && isPalindrom（str。substr（1， len -2））；
}
}
對比一下，是不是簡單很多？我們也不需要理解是判斷完外部後，裡面的內部內容怎麼判斷的，只需要知道對於內部的字串，操作方式跟此時的一樣就行了。
The Towers of Hanoi
19世紀80年代由法國數學家Edouard Lucas發明的Hanoi難題塔在歐洲迅速普及。它的成功部分原因是由於法國數學家Henri De Parville（由數學歷史學家W。 W。 R。 Ball翻譯）在La Nature中描述的這個謎題古老的傳說。
在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：
一次只移動一片，
不管在哪根針上，小片必須在大片上面。
僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。
現在，這個謎題已經作為了一個趣味的兒童益智遊戲，64個金牌的傳奇被八個木製或塑膠片替代，這使得遊戲更容易解決。所以，初始的疑題看起來是這樣子的：
如圖，我們要做的是在上述的規則把盤子從A移動到B中。
為了更好的解決這個問題。我們需要建立一箇中轉站，用來存放臨時從A這裡開始挪動的盤子。
如果我們按部就班，從上取一個，移動到某一根針，這樣我們就會產生倒三角。不符合規則。按常規思路是比較複雜的。我們試試從遞迴的角度看待。
先從整體的角度，這個問題的最後，一定是在C上是前面7個塑膠片的正確排序，此時A裡遺留的是最底下的一片最大的。因此我們要做的就是把它從A挪動到B中，再把C中的所有盤子挪動到B中完成目標。
當碟片只有7片的時候，我們同樣可以使用這種方式操作。
在遞迴的思想中，我們不關心他們是怎麼把A中的盤子平移到C的，我們只需要知道當盤子為7的時候，我們這麼做也可以達到目的。
我們把A定義為start，把B定義為end，把C定義為temp，則當盤子為N的時候，我們可以這樣操作：
將前面的N-1個盤子全部移動到C
把底下的最大的盤子移動到B
將C中的N-1盤子移動到B
當盤子總數為7的時候，我們也可以用同樣的辦法處理剩下的。
總結好了一般的做法，接下來我們來找simple case。什麼情況下我們不需要這樣做了呢？試想我們如果只有一個盤子，我們是怎麼做的？只需要將盤子從A到B就可以了，這樣就不用透過中轉站，擺脫遞迴了。
因此我們的遞迴函式應該是這樣寫的：
void
moveTower
（
int
n
，
char
start
，
char
finish
，
char
tmp
）
{
if
（
n
==
1
）
{
//將盤子從A移動到B
}
else
{
//將前面的N-1個盤子全部移動到C（temp）
//把底下的最大的盤子移動到B（finish）
//將C（temp）中的N-1盤子移動到B（finsh）
}
}
假設我們的單個移動的函式是這樣定義的：
void moveSingleDisk（char start， char finish） {
cout << start << “ -> ” << finish << endl；
}
而我們通常情況下的移動是這樣的：
void moveTower（int n， char start， char finish， char tmp）
我們的程式碼就應該是這樣的：
void moveTower（int n， char start， char finish， char tmp） {
if （n == 1） {
moveSingleDisk（start， finish）；
} else {
moveTower（n - 1， start， tmp， finish）；
moveSingleDisk（start， finish）；
moveTower（n - 1， tmp， finish， start）；
}
}
乍一看好像有點匪夷所思，但這確實是根據我們的遞迴思想作出的結論跟寫出的程式碼。我們完全可以 證實一下程式碼是否能正確執行。
