6.5　遞歸

視頻講解

6.5.1　遞歸是什么

本節小甲魚將通過生動的講解，告訴大家什么是遞歸。如果說優秀的程序員是伯樂，那么把遞歸比喻成“神馬”是再形象不過的了。

遞歸到底是什么東西呢？有那么厲害嗎？為什么大家常說“普通程序員用迭代，天才程序員用遞歸”呢？沒錯，通過本節的學習，你將了解遞歸，通過獨立完成小甲魚精心配套的課后作業，將徹底擺脫遞歸給你生活帶來的困擾。

遞歸這個概念，是算法的范疇，本來不屬于Python語言的語法內容，但小甲魚基本在每個編程語言系列教學里都要講遞歸，那是因為如果掌握了遞歸的方法和技巧，會發現這是一個非常棒的編程思路。

那么，遞歸算法在日常編程中有哪些例子呢？

（1）漢諾塔游戲（如圖6-1所示）。

（2）樹結構的定義（如圖6-2所示）。

圖6-1　漢諾塔游戲

圖6-2　樹結構的定義

（3）謝爾賓斯基三角形（如圖6-3所示）。

（4）女神自拍（如圖6-4所示）。

說了這么多，在編程上，遞歸是什么這個概念還沒講呢！遞歸，從原理上來說就是函數調用自身的行為。你沒聽錯，在函數內部可以調用所有可見的函數，當然也包括它自己。

圖6-3　謝爾賓斯基三角形

圖6-4　女神自拍

舉個例子：

這個例子嘗試了初學者玩遞歸最容易出現的錯誤。從理論上來講，這個程序將永遠執行下去直至耗盡所有內存資源。不過Python 3出于“善意的保護”，對遞歸深度默認是有限制的，所以上面的代碼才會停下來。不過如果是編寫網絡爬蟲工具，可能會“爬”得很深，那樣的話就需要自行設置遞歸的深度限制了。方法如下：

     >>> import sys
     >>> sys.setrecursionlimit(10000)  # 將遞歸深度限制設置為一萬層

上面的例子由于錯誤地使用遞歸，一不小心就把Python給“干掉了”，可見遞歸的威力之大。使用sys.setrecursionlimit(10000)雖然可以設置遞歸的深度，但如果設置的值太大（如100000000），那么程序也可能會崩潰，這時可以通過Ctrl+C快捷鍵讓Python強制停止。

6.5.2　寫一個求階乘的函數

正整數的階乘是指從1乘以2乘以3乘以4一直乘到所要求的數。例如所要求的數是5，則階乘式是1×2×3×4×5，得到的積是120，所以120就是5的階乘。好，那大家先自己嘗試下實現一個非遞歸版本：

程序實現結果如下：

     >>>
     請輸入一個正整數：5
     5 的階乘是：120

普通函數的實現相信大家都會寫，那再來演示一下遞歸版本：

以前沒接觸過遞歸的小伙伴肯定會懷疑這是否能正常執行？沒錯，這完全符合遞歸的預期和標準，所以函數無疑可以正確執行并返回正確的結果，程序實現結果與非遞歸版本的結果是一樣的：

     >>>
     請輸入一個正整數：5
     5 的階乘是：120

麻雀雖小，卻五臟俱全。這個例子滿足了遞歸的兩個條件：

?　調用函數本身。

?　設置了正確的返回條件。

請看詳細分析，如圖6-5所示。

圖6-5　遞歸函數的實現分析

最后要鄭重地說一下“普通程序員用迭代，天才程序員用遞歸”這句話是不無道理的。但是不要理解錯了，不是說會使用遞歸，把所有能迭代的東西用遞歸來代替就是“天才程序員”了，恰好相反，如果你真的這么做的話，那你就是“烏龜程序員”啦。為什么這么說呢？不要忘了，遞歸的實現可是函數自己調用自己，每次函數的調用都需要進行壓棧、彈棧、保存和恢復寄存器的棧操作，所以在這上面是非常消耗時間和空間的。

另外，如果遞歸一旦忘記了返回，或者錯誤地設置了返回條件，那么執行這樣的遞歸代碼就會變成一個無底洞：只進不出！所以在寫遞歸代碼的時候，千萬要記住口訣：遞歸遞歸，歸去來兮！

因此，結合以上兩點致命缺陷，很多初學者經常就會在論壇上討論遞歸存在的必要性，他們認為遞歸完全沒必要，用循環就可以實現。其實這就像是在討論C語言好還是Python更優秀一樣，是沒有必要的。因為一樣東西既然能夠持續存在，那必然有它存在的道理。遞歸用在妙處，代碼自然簡潔、精練，所以說“天才程序員使用遞歸”。

6.5.3　一幫小兔子——斐波那契數列

視頻講解

按理來說，今天的話題與兔子不搭邊，不過大家也知道小甲魚的風格——天南地北總能將看似無關的東西扯到一起，所以本節就講講如何用遞歸實現斐波那契（Fibonacci）數列。

斐波那契數列的發明者，是意大利數學家列昂納多·斐波那契（Leonardo Fibonacci）。當年這個數列是由兔子交配的故事開始講起的：假如說兔子在出生兩個月后，就有了繁殖能力，此后這對兔子在接下來的每個月都能生出一對可愛的小兔子。假設所有兔子都不會老去，就這么一直折騰下去，那么一年以后可以繁殖多少對兔子出來呢？

我們都知道兔子繁殖能力是驚人的，如圖6-6所示。

圖6-6　斐波那契數列

數據統計如表6-1所示。

表6-1　斐波那契數列

可以用數學函數來定義，如下：

假設需要求出經歷了20個月后，總共有多少對小兔子，不妨考慮一下分別用迭代和遞歸如何實現？

迭代實現：

接下來看看遞歸的實現原理，如圖6-7所示。

圖6-7　遞歸實現斐波那契數列的原理

遞歸實現：

可見邏輯非常簡單，直接把所想的東西寫成代碼就是遞歸算法了。不過，之前總說遞歸如果使用不當，效率會很低，但是有多低呢？這就來證明一下。我們試圖把20個月修改為35個月，然后試試看把程序執行起來。

發現了吧，用迭代代碼來實現基本是毫秒級的，而用遞歸來實現就考驗你的CPU能力啦（N秒~N分鐘不等）。這就是小甲魚不支持大家所有東西都用遞歸求解的原因，本來好好的一個代碼，用了遞歸，效率反而拉下了一大截。

為了體現遞歸正確使用的優勢，下一節來談談利用遞歸解決漢諾塔難題。如果不懂得遞歸，試圖想要寫個程序來解決問題是相當困難的，但如果使用了遞歸，你會發現問題奇跡般得變簡單了！

6.5.4　漢諾塔

視頻講解

漢諾塔（如圖6-8所示）的來源據說是這樣的：一位法國數學家曾經編寫過一個印度的古老傳說。說的是在世界中心貝拿勒斯的圣廟里邊，有一塊黃銅板，上面插著三根寶針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。然后不論白天或者黑夜，總有一個僧侶按照下面的法則來移動這些金片：“一次只移動一片，不管在哪根針上，小片必須在大片上面。”規則很簡單，另外僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

圖6-8　漢諾塔

要解決一個問題，大家說什么最重要？沒錯，思路！思路有了，問題就可以隨之迎刃而解。

對于游戲的玩法，可以簡單分解為三個步驟：

（1）將前63個盤子從X移動到Y上，確保大盤在小盤下。

（2）將最底下的第64個盤子從X移動到Z上。

（3）將Y上的63個盤子移動到Z上。

這樣看上去問題就簡單一點了，有讀者會說小甲魚你這不廢話嘛，說與沒說一樣！因為步驟（1）和步驟（3）應該如何執行才是讓人頭疼的問題。

但是仔細思考一下，在游戲中，我們發現由于每次只能移動一個圓盤，所以在移動的過程中顯然要借助另外一根針才可以實施。也就是說，步驟（1）需要借助Z將1~63個盤子移到Y上，步驟（3）需要借助X將Y針上的63個盤子移到Z針上。

所以把新的思路聚集為以下兩個問題：

問題一，將X上的63個盤子借助Z移到Y上。

問題二，將Y上的63個盤子借助X移到Z上。

然后我們驚奇地發現，解決這兩個問題的方法與剛才第一個問題的思路是一樣的，都可以拆解成三個步驟來實現。

問題一（將X上的63個盤子借助Z移到Y上）拆解為：

（1）將前62個盤子從X移動到Z上，確保大盤在小盤下。

（2）將最底下的第63個盤子移動到Y上。

（3）將Z上的62個盤子移動到Y上。

問題二（將Y上的63個盤子借助X移到Z上）拆解為：

（1）將前62個盤子從Y移動到X上，確保大盤在小盤下。

（2）將最底下的第63個盤子移動到Z上。

（3）將X上的62個盤子移動到Y上。

說到這里，是不是發現了什么？沒錯，漢諾塔的拆解過程剛好滿足遞歸算法的定義，因此，對于如此難題，使用遞歸來解決，問題就變得相當簡單。

參考代碼：

看，這就是遞歸的魔力：

     >>>
     請輸入漢諾塔的層數：3
     X --> Z
     X --> Y
     Z --> Y
     X --> Z
     Y --> X
     Y --> Z
     X --> Z