前面談到了遞歸的一些思想，還有概念上的一些理解，這里試著用遞歸解決一些問題。比如回文。

回文是一種字符串，它正著讀和反著讀都是一樣的。比如level,eye都是回文。用迭代的方法可以很快地判斷一個(gè)字符串是否為回文。用遞歸的方法如何來實(shí)現(xiàn)呢？

首先我們要考慮使用遞歸的兩個(gè)條件：

• 第一：這個(gè)問題是否可以分解為形式相同但規(guī)模更小的問題？
• 第二：如果存在這樣一種分解，那么這種分解是否存在一種簡(jiǎn)單情境？

先來看第一點(diǎn)，是否存在一種符合條件的分解。容易發(fā)現(xiàn)，如果一個(gè)字符串是回文，那么在它的內(nèi)部一定存在著更小的回文。 比如level里面的eve也是回文。 而且，我們注意到，一個(gè)回文的第一個(gè)字符和最后一個(gè)字符一定是相同的。

所以我們很自然的有這樣的方法：

先判斷給定字符串的首尾字符是否相等，若相等，則判斷去掉首尾字符后的字符串是否為回文，若不相等，則該字符串不是回文。

注意，我們已經(jīng)成功地把問題的規(guī)模縮小了，去掉首尾字符的字符串當(dāng)然比原字符串小。

接著再來看第二點(diǎn)， 這種分解是否存在一種簡(jiǎn)單情境呢？簡(jiǎn)單情境在使用遞歸的時(shí)候是必須的，否則你的遞歸程序可能會(huì)進(jìn)入無止境的調(diào)用。

對(duì)于回文問題，我們?nèi)菀装l(fā)現(xiàn)，一個(gè)只有一個(gè)字符的字符串一定是回文，所以，只有一個(gè)字符是一個(gè)簡(jiǎn)單情境，但它不是唯一的簡(jiǎn)單情境，因?yàn)榭兆址彩腔匚?。這樣，我們就得到了回文問題的兩個(gè)簡(jiǎn)單情境：字符數(shù)為1和字符數(shù)為0。

好了，兩個(gè)條件都滿足了，基于以上分析，我們可以很容易的編寫出解決回文問題的遞歸實(shí)現(xiàn)方式：

程序運(yùn)行結(jié)果為：