6.1 Python的樂高積木
小時候大家應該都玩過樂高積木，只要通過想像和創意，可以用它拼湊出很多神奇的東西。隨著學習的深入，編寫的代碼日益增加並且越來越複雜，所以需要找一個方法對這些複雜的代碼進行重新組織。這麼做的目的是使得代碼更為簡單易懂。我們說優秀的東西永遠是經典的，而經典的東西永遠是簡單的。不是說複雜不好，要能夠把複雜的東西簡單化才能成為經典。
為了使得程式的代碼更為簡單，就需要把程式分解成較小的組成部分。這裡會教大家三種方法來實現，分別是函數、物件和模組。
6.1.1 創建和調用函數
函數就是把代碼打包成不同形狀的樂高積木，以便可以發揮想像力進行隨意拼裝和反復使用。此前接觸的BIF就是Python幫我們封裝好的函數，用的時候很方便，根本不需要去想實現的原理，這就是把複雜變簡單。
因為這幾部分內容奠定了Python程式設計者的基本功底，所以小甲魚在這幾部分的準備上是花足了心思的，大家不要嫌囉唆——經常變著花樣兒重複出現的內容肯定是最重要的。
簡單來講，一個程式可以按照不同功能的實現，分割成許許多多的代碼塊，每一個代碼塊就可以封裝成一個函數。在Python中創建一個函數用def關鍵字：
注意，在函數名後邊要加上一對小括弧哦。這對小括弧是必不可少的，因為有時候需要在裡邊放點東西，至於放什麼，小甲魚先賣個關子，待會兒告訴你。
我們創建了一個函數，但是從來都不去調用它，那麼這個函數裡的代碼就永遠也不會被執行。這裡教大家如何調用一個函數。調用一個函數也非常簡單，直接寫出函數名加上小括弧即可：
函數的調用和運行機制：當函數myFirstFunction()發生調用操作的時候，Python會自動往上找到def
myFirstFunction()的定義過程，然後依次執行該函數所包含的代碼塊部分（也就是冒號後邊的縮進部分內容）。只需要一條語句，就可以輕鬆地實現函數內的所有功能。假如我想把剛才的內容列印3次，我只需要調用3次函數即可：
6.1.2 函數的參數
現在可以來談談括弧裡是什麼東西了！其實括弧裡放的就是函數的參數。在函數剛開始被發明出來的時候，是沒有參數的（也就是說，小括弧裡沒有內容），很快就引來了許多小夥伴們的質疑：函數不過是對做同樣內容的代碼進行打包，這樣跟使用迴圈就沒有什麼本質不同了。
所以，為了使每次調用的函數可以有不同的實現，加入了參數的概念。例如，你封裝了一個開炮功能的函數，預設武器是大炮，那用來打飛機是沒問題的，但是你如果用這個函數來打小鳥，除非是憤怒的小鳥，否則就有點奇葩了。有了參數的實現，就可以輕鬆地將大炮換成步槍。總而言之，參數就是使得函數可以實現個性化：
剛才的例子只有一個參數，使用多個參數，只需要用逗號隔開即可：
那有些讀者要問了，到底Python的函數支援多少參數呢？實際上你想要有多少個參數就可以有多少個參數，就像Windows的某些API函數就有十幾個參數。但是建議大家自己定義的函數參數儘量不要太多，函數的功能和參數的意義也要相應寫好注釋，這樣別人來維護你的程式才不會那麼費勁！
6.1.3 函數的返回值
有些時候，需要函數為我們返回一些資料來報告執行的結果，譬如剛才提到具有開炮功能的函數，炮彈發射了之後到底是打中了沒有？你總得有個交代吧。所以，我們的函數需要返回值。其實也非常簡單，只需要在函數中使用關鍵字return，後邊跟著的就是指定要返回的值：
6.2 靈活即強大
有時候，評論一種程式設計語言是否優秀，往往是看它是否靈活。靈活並非意味著無所不能、無所不包，那樣就會顯得龐大和冗雜。靈活應該表現為多變，比如前面學到的參數，函數因參數而靈活。如果沒有參數，一個函數就只能死板地完成一個功能、一項任務。
6.2.1 形參和實參
參數從調用的角度來說，分為形式參數（parameter）和實際參數（argument）（注：本書後邊簡稱為形參和實參）。跟絕大多數程式設計語言一樣，形參指的是函數創建和定義過程中小括弧裡的參數，而實參則指的是函數在被調用的過程中傳遞進來的參數。舉個例子：
myFristFunction(name)的name是形參，因為它只是代表一個位置、一個變數名；而調用myFirstFunction（＂小甲魚＂）傳遞的＂小甲魚＂是實參，因為它是一個具體的內容，是賦值到變數名中的值！
6.2.2 函數文檔
給函數寫文檔是為了讓別人可以更好地理解你的函數，所以這是一個好習慣。有些讀者可能不理解為什麼自己寫的函數要跟別人分享呢？因為在實際開發中，個人的工作量和能力確實相當有限，因此中大型的程式永遠都是團隊來完成的。大家的代碼要相互銜接，就需要先閱讀別人提供的文檔，因此適當的文檔說明非常重要。而函數文檔的作用是描述該函數的功能，當然，這是寫給人看的：
我們看到，在函數開頭寫下的字串是不會列印出來的，但它會作為函數的一部分存儲起來。這個稱為函數文檔字串，它的功能跟注釋是一樣的。
那有讀者可能會說，既然一樣，搞那麼複雜幹啥呀？其實也不是完全一樣，函數的文檔字串可以通過特殊屬性__doc__獲取（注：__doc__兩邊分別是兩條底線）：
另外，想用一個函數卻不確定其用法的時候，會通過help()函數來查看函數的文檔。因此，對我們自己的函數也可以依法炮製：
6.2.3 關鍵字參數
普通的參數叫位置參數，通常在調用一個函數的時候，粗心的程式師很容易會搞亂位置參數的順序，以至於函數無法按照預期實現。因此，有了關鍵字參數。使用關鍵字參數，就可以很簡單地解決這個潛在的問題，來看個例子：
關鍵字參數其實就是在傳入實參時指定形參的變數名，儘管使用這種技巧要多打一些字，但隨著程式規模越來越大、參數越來越多，關鍵字參數起到的作用就越明顯。畢竟寧可多打幾個字元，也不希望出現料想不及的BUG。
6.2.4 默認參數
初學者很容易搞混關鍵字參數和默認參數，默認參數是在定義的時候賦予了預設值的參數：
使用默認參數的話，就可以不帶參數去調用函數。所以，它們之間的區別是：關鍵字參數是在函式呼叫的時候，通過參數名指定要賦值的參數，這樣做就不怕因為搞不清參數的順序而導致函式呼叫出錯；而默認參數是在參數定義的過程中，為形參賦初值，當函式呼叫的時候，不傳遞實參，則默認使用形參的初始值代替。
6.2.5 收集參數
這個名字聽起來比較新鮮，其實大多數時候它也被稱作可變參數。發明這種機制的動機是函數的作者有時候也不知道這個函數到底需要多少個參數……聽起來有點令人不解，但確實有這類情況。這時候，僅需要在參數前邊加上星號（*）即可：
其實大家仔細思考後也不難理解，Python就是把標誌為收集參數的參數們打包成一個元組。不過這裡需要注意一下，如果在收集參數後邊還需要指定其他參數，在調用函數的時候就應該使用關鍵參數來指定，否則Python就都會把你的實參都列入收集參數的範疇。舉個例子：
建議大家如果你的參數中帶有收集參數，那麼可將其他參數設置為默認參數，這樣不容易出錯：
星號（*）其實既可以打包又可以“解包”。“解包”又是怎麼回事呢？舉個例子，假如你需要將一個清單a傳入test參數的收集參數* param中，那麼調用test(a)時便會出錯，此時需要在a前邊加上個星號（*）表示實參需要“解包”後才能使用：
Python還有另一種收集方式，就是用兩個星號（**）表示。跟前面的介紹不同，兩個星號的收集參數表示為將參數們打包成字典的形式。字典的概念還沒有接觸，所以在後邊講解字典的章節中再給大家介紹吧。
6.3 我的地盤聽我的
6.3.1 函數和過程
在很多程式設計語言中，函數和過程其實是區分開的。一般認為函數（function）是有返回值的，而過程（procedure）是簡單、特殊並且沒有返回值的。也就是說，函數是幹完事兒必須寫報告的“苦逼”，而過程是完事後拍拍屁股一走了之的“小混蛋”。
Python嚴格來說只有函數，沒有過程！此話怎講？有些朋友可能會說，在沒有介紹return之前，Python的函數不也沒有返回值嗎？此言差矣，為了讓大家更好地理解“Python嚴格來說只有函數，沒有過程！”這句話，大家一起看看下面的例子：
調用print(hello())之後列印了兩行文字，第一行我們當然知道是hello()函數執行的，第二行的None是怎麼回事？沒錯，大家猜對了。當不寫return語句的時候，預設Python會認為函數是return
None的。所以說Python所有的函數都有返回值。
6.3.2 再談談返回值
在許多程式設計語言中，我們說一個函數是整型，其實我們的意思是指這個函數會返回一個整型的返回值。而Python不這麼幹，Python可以動態確定函數的類型，而且函數還能返回不同類型的值。還記得以前說過“Python沒有變數，只有名字”這句話嗎？只需知道Python會返回一個東西，然後拿來用就可以了。另外，Python似乎還可以同時返回多個值：
Python可以利用列表打包多種類型的值一次性返回。當然，你也可以直接用元組的形式返回多個值：
6.3.3 函數變數的作用域
其實這裡要談的是函數變數的作用域，也許你早已經聽說了區域變數和全域變數，也許你早已經熟練於其他程式設計語言的變數作用域的細節，但無論如何這裡你要認真學，因為這是重點，也許真有你平時注意不到的細節呢。
變數的作用域也就是平時所說的變數可見性，如上所說，一般的程式設計語言都有區域變數（Local
Variable）和全域變數（Global
Variable）之分。分析以下代碼：
程式執行結果如下：
來分析一下代碼：在函數discounts()中，兩個參數是price和rate，還有一個是final_price，它們都是discounts()函數中的區域變數。為什麼把它們稱為區域變數呢？不妨修改一下代碼：
程式走起，像剛才一樣輸入之後程式便報錯了：
錯誤原因：final_price沒有被定義過，也就是說，Python找不到final_price這個變數。這是因為final_price只是一個區域變數，它的作用範圍只在它的地盤上——discounts()函數的定義範圍內——有效，出了這個範圍，就不再屬於它的地盤了，它將什麼都不是。
總結一下：在函數裡邊定義的參數以及變數，都稱為區域變數，出了這個函數，這些變數都是無效的。事實上的原理是，Python在運行函數的時候，利用棧（Stack）進行存儲，當執行完該函數後，函數中的所有資料都會被自動刪除。所以在函數外邊是無法訪問到函數內部的區域變數的。
與區域變數相對的是全域變數，程式中old_price、new_price、rate都是在函數外邊定義的，它們都是全域變數，全域變數擁有更大的作用域，例如在函數中可以訪問到它們：
程式執行結果如下：
真的可以實現，看上去似乎全域變數更為霸道！不過使用全域變數的時候要千萬小心，在任何一種程式設計語言中都是如此。在Python中，你可以在函數中肆無忌憚地訪問一個全域變數，但如果你試圖去修改它，就會有奇怪的事情會發生了。分析下面的代碼：
程式執行結果如下：
這裡我就不吊大家的胃口了，如果在函數內部試圖修改全域變數，那麼Python會創建一個新的區域變數替代（名字跟全域變數相同），但真正的全域變數是紋絲不動的，所以實現的結果和大家的預期不同。
關於全域變數，我們也來總結一下：全域變數在整個程式碼片段中都是可以訪問到的，但是不要試圖在函數內部去修改全域變數的值，因為那樣Python會自動在函數內部新建一個名字一樣的區域變數代替。
對於初學者來說，區域變數和全域變數在使用上很容易犯錯，尤其是很多朋友都試圖去建立一個跟全域變數同名的區域變數，這類做法小甲魚是強烈反對的。那我如果想在函數裡邊去修改全域變數的值，有辦法實現嗎？如果我在函數裡邊想嵌套定義一個新的函數，可以嗎？這些問題的答案都是肯定的，不過我們將在下一節再跟大家詳細講解。
6.4 內嵌函數和閉包
6.4.1 global關鍵字
全域變數的作用域是整個模組（整個程式碼片段），也就是程式碼片段內所有的函數內部都可以訪問到全域變數。但要注意的一點是，在函數內部僅僅去訪問全域變數就好，不要試圖去修改它。
因為那樣的話，Python會使用遮罩（Shadowing）的方式“保護”全域變數：一旦函數內部試圖修改全域變數，Python就會在函數內部自動創建一個名字一模一樣的區域變數，這樣修改的結果只會修改到區域變數，而不會影響到全域變數。看下面的例子：
但是畢竟人是要靈活應變的，假設你已經完全瞭解在函數中修改全域變數可能會導致程式可讀性變差、出現莫名其妙的BUG、代碼的維護成本提高，但你還是堅持“虛心接受，死性不改”這八字原則，仍然覺得有必要在函數中去修改這個全域變數，那麼你不妨可以使用global關鍵字來達到目的！修改程式如下：
6.4.2 內嵌函數
Python的函式定義是可以嵌套的，也就是允許在函數內部創建另一個函數，這種函數叫作內嵌函數或者內建函式。接著看另一個例子：
這是函數嵌套的最簡單的例子，雖然看起來沒什麼用……不過它麻雀雖小，五臟俱全。關於內建函式的使用，有一個比較值得注意的地方，就是內建函式整個作用域都在外部函數之內。就像剛才例子中的fun2()整個函數的作用域都在fun1()裡邊。
需要注意的地方是，除了在fun1()這個函數體中可以隨意調用fun2()這個內建函式外，出了fun1()，就沒有任何可以對fun2()進行的調用。如果在fun1()外部試圖調用內建函式fun2()，就會報錯：
6.4.3 閉包（closure）
閉包（closure）是函數式程式設計的一個重要的語法結構，函數式程式設計是一種程式設計範式，著名的函數式程式設計語言就是LISP語言（大家可能聽說過這門語言，主要應用於繪圖和人工智慧，一直被認為是天才程式師使用的語言）。
那麼不同的程式設計語言實現閉包的方式不同，Python中的閉包從表現形式上定義為：如果在一個內建函式裡，對在外部作用域（但不是在全域作用域）的變數進行引用，那麼內建函式就被認為是閉包（closure）。還是來舉個例子說明比較好理解：
也可以直接這麼寫：
通過上面的例子理解閉包的概念：如果在一個內建函式裡（funY就是這個內建函式）對外部作用域（但不是在全域作用域）的變數進行引用（x就是被引用的變數，x在外部作用域funX函數裡面，但不在全域作用域裡），則這個內建函式（funY）就是一個閉包。
使用閉包需要注意的是：因為閉包的概念就是由內建函式而來的，所以你也不能在外部函數以外的地方對內建函式進行調用，下面的做法是錯誤的：
在閉包中，外部函數的區域變數對應內建函式的區域變數，事實上相當於之前講的全域變數跟區域變數的對應關係，在內建函式中，你只能對外部函數的區域變數進行訪問，但不能進行修改。
這個報錯資訊跟之前講解全域變數的時候基本一樣，Python認為在內建函式的x是區域變數的時候，外部函數的x就被遮罩了起來，所以執行x * = x的時候，在右邊根本就找不到區域變數x的值，因此報錯。
在Python3以前並沒有直接的解決方案，只能間接地通過容器類型來存放，因為容器類型不是放在棧裡，所以不會被“遮罩”掉。容器類型這個詞兒大家是不是似曾相識？之前介紹的字串、清單、元組，這些啥都可以往裡的放的就是容器類型。於是可以把代碼改造如下：
到了Python3的世界裡，有了不少的改進。如果希望在內建函式裡可以修改外部函數裡的區域變數的值，那麼也有一個關鍵字可以使用，就是nonlocal，使用方式跟global一樣：
擴展閱讀->遊戲中的移動角色：閉包（closure）在實際開發中的作用（地址是http://bbs.fishc.com/thread-42656-1-1.html）。
6.5 lambda運算式
Python允許使用lambda關鍵字來創建匿名函數。我們提到一個新的關鍵字——匿名函數。那什麼是匿名函數呢？匿名函數跟普通函數在使用上又有什麼不同呢？使用匿名函數又有怎樣的優勢呢？
那先來談談lambda運算式怎麼用，然後再來討論它的意義吧。先來定義一個普通的函數：
如果使用lambda語句來定義這個函數，就會變成這樣：
Python的lambda運算式語法非常精簡（符合Python的風格），基本語法是在冒號（：）左邊放原函數的參數，可以有多個參數，用逗號（，）隔開即可；冒號右邊是返回值。在上面的例子中我們發現lambda語句實際上是返回一個函數物件，如果要對它進行使用，只需要進行簡單的賦值操作即可：
下面演示lambda運算式帶兩個參數的例子：
lambda運算式的作用：
（1）Python寫一些執行腳本時，使用lambda就可以省下定義函數過程，比如說只是需要寫個簡單的腳本來管理伺服器時，就不需要專門定義一個函數然後再寫調用，使用lambda就可以使得代碼更加精簡。
（2）對於一些比較抽象並且整個程式執行下來只需要調用一兩次的函數，有時候給函數起個名字也是比較頭疼的問題，使用lambda就不需要考慮命名的問題了。
（3）簡化代碼的可讀性，由於閱讀普通函數經常要跳到開頭def定義的位置，使用lambda函數可以省去這樣的步驟。
介紹兩個BIF：filter()和map()
接下來給大家介紹Python在實際應用中比較實用的兩個BIF，這兩個BIF使用比起之前一步到位的內建函數來說，相對要複雜一點，也嘗試著把今天學到的lambda運算式結合在一起。
1．filter()
我們研究的第一個內建函數是一個篩檢程式。我們每天會接觸到大量的資料，篩檢程式的作用就顯得非常重要了，通過篩檢程式，就可以保留你所關注的資訊，把其他不感興趣的東西直接丟掉。這麼講大家應該就瞭解了，那Python的這個filter()如何來實現過濾的功能呢？先來看下Python自己的注釋：
大概意思是：filter有兩個參數。第一個參數可以是一個函數也可以是None，如果是一個函數的話，則將第二個可反覆運算資料裡的每一個元素作為函數的參數進行計算，把返回True的值篩選出來；如果第一個參數為None，則直接將第二個參數中為True的值篩選出來。
這麼說有些朋友可能還不大理解，小甲魚還是用簡單的例子幫助解釋一下吧：
利用filter()，嘗試寫一個篩選奇數的篩檢程式：
那現在學習lambda運算式後，完全可以把上述過程轉化成一行：
2．map()
map在這裡不是地圖的意思，在程式設計領域，map一般作“映射”來解釋。map()這個內置函數也有兩個參數，仍然是一個函數和一個可反覆運算序列，將序列的每一個元素作為函數的參數進行運算加工，直到可反覆運算序列每個元素都加工完畢，返回所有加工後的元素構成的新序列。
有了剛才filter()的經驗，這裡舉個例子讓大家知道map()的用法：
6.6 遞迴
6.6.1 遞迴是“神馬”
本節的主題叫遞迴是“神馬”，小甲魚將通過帶感的講解，來告訴大家“神馬”是遞迴。如果說優秀的程式師是伯樂，那麼把遞迴比喻成神馬是再形象不過的了！
遞迴到底是什麼東西呢？有那麼厲害嗎？為什麼大家常說“普通程式師用反覆運算，天才程式師用遞迴”呢？沒錯，通過本節的學習，你將瞭解遞迴，通過獨立完成課後佈置的練習，你將徹底擺脫遞迴給你生活帶來的困擾！
遞迴這個概念，是演算法的範疇，本來不屬於Python語言的語法內容，但小甲魚基本在每個程式設計語言系列教學裡都要講遞迴，那是因為如果你掌握了遞迴的方法和技巧，你會發現這是一個非常棒的程式設計思路！
那麼遞迴演算法在日常程式設計中有哪些例子呢？
漢諾塔遊戲如圖6-1所示。
圖6-1 漢諾塔遊戲
樹結構的定義如圖6-2所示。
圖6-2 樹結構的定義
謝爾賓斯基三角形如圖6-3所示。
圖6-3 謝爾賓斯基三角形
女神自拍如圖6-4所示。
圖6-4 女神自拍
說了這麼多，在程式設計上，遞迴是什麼這個概念還沒講呢！遞迴，從原理上來說就是函式呼叫自身這麼一個行為。你沒聽錯，在函數內部你可以調用所有可見的函數，當然也包括自己。舉個例子：
這個例子嘗試了初學者玩遞迴最容易出現的錯誤。從理論上來講，這個程式將永遠執行下去直至耗盡所有記憶體資源。不過Python3出於“善意的保護”，對遞迴的深度默認限制是100層，所以你的代碼才會停下來。不過如果你寫網路爬蟲等工具，可能會爬很深，那你也可以自己設置遞迴的深度限制。方法如下：
剛才一來就錯誤地使用遞迴把Python幹掉了，可見遞迴的厲害和危險，這個後邊講，接下來舉個正常的例子跟大家完整解釋一下遞迴。噢，對了，如果你真的設置了一百萬層遞迴，那麼一不小心又玩脫了，Python可能會卡在那裡很久，這時你可以通過Ctrl+C讓它停止哦。
6.6.2 寫一個求階乘的函數
正整數的階乘是指從1乘以2乘以3乘以4一直乘到所要求的數。例如所要求的數是5，則階乘式是1×2×3×4×5，得到的積是120，所以120就是5的階乘。好，那大家先自己嘗試下實現一個非遞迴版本：
程式實現結果如下：
普通函數的實現相信大家都會寫，那再來演示一下遞迴版本：
以前沒接觸過遞迴的小夥伴肯定會懷疑這是否能正常執行？沒錯，這完全符合遞迴的預期和標準，所以函數無疑可以正確執行並返回正確的結果！程式實現結果跟上邊的結果是一樣的：
我們說過，麻雀雖小，卻五臟俱全。這個例子滿足了遞迴的兩個條件：
（1）調用函數本身。
（2）設置了正確的返回條件。
上面程式的詳細分析如圖6-5所示。
圖6-5 遞迴函數的實現分析
最後要鄭重說一下“普通程式師用反覆運算，天才程式師用遞迴”這句話是不無道理的。但是你不要理解錯了，不是說會使用遞迴，把所有能反覆運算的東西用遞迴來代替就是“天才程式師”了，恰好相反，如果你真的這麼做的話，那你就是“烏龜程式師”啦。為什麼這麼說呢？不要忘了，遞迴的實現可以是函數自個兒調用自個兒，每次函數的調用都需要進行壓棧、彈棧、保存和恢復寄存器的棧操作，所以在這上邊是非常消耗時間和空間的。
另外，如果遞迴一旦忘記了返回，或者錯誤地設置了返回條件，那麼執行這樣的遞迴代碼就會變成一個無底洞：只進不出！所以在寫遞迴代碼的時候，千萬要記住口訣：遞迴遞迴，歸去來兮！
因此，結合以上兩點致命缺陷，很多初學者經常就會在論壇上討論遞迴存在的必要性，他們認為遞迴完全沒必要，用迴圈就可以實現。其實這就跟討論C語言好還是Python優秀一樣，是沒有必要的。因為一樣東西既然能夠持續存在，那必然有它存在的道理。遞迴用在妙處，自然代碼簡潔、精練，所以說“天才程式師使用遞迴”。
6.6.3 這幫小兔崽子
按理來說，今天的話題跟兔子不拉邊，不過嘛，大家也知道小甲魚的風格了，天南地北，總有相關聯的東西可以拉過來扯淡。本節就用遞迴來實現斐波那契（Fibonacci）數列吧。
斐波那契數列的發明者，是義大利數學家列昂納多·斐波那契（Leonardo Fibonacci）。這老頭說來跟小甲魚也有一定的淵源，就是老愛拿動物交配說事兒，不同的是小甲魚注重過程和細節，而這老頭更關心結果，下邊就有一個他講過的故事：如果說兔子在出生兩個月後，就有繁殖能力，在擁有繁殖能力之後，這對兔子每個月能生出一對小兔子來。假設所有兔子都不會死去，能夠一直幹下去，那麼一年之後可以繁殖多少對兔子呢？
我們都知道兔子繁殖能力是驚人的，如圖6-6所示。
圖6-6 斐波那契數列
資料統計如表6-1所示。
表6-1 斐波那契數列
可以用數學函數來定義，如圖6-7所示。
圖6-7 求斐波那契數列的公式
假設需要求出經歷了20個月後，總共有多少對小兔崽子，不妨一起考慮一下分別用反覆運算和遞迴如何實現？
反覆運算實現：
接下來看看遞迴的實現原理，如圖6-8所示。
圖6-8 遞迴實現斐波那契數列的原理
遞迴實現：
可見邏輯非常簡單，直接把想的東西寫成代碼就是遞迴演算法了。不過，之前我們總說遞迴如果使用不當，效率會很低，但是有多低呢？我們這就來證明一下。我們試圖把20個月修改為35個月，然後試試看把程式執行起來……
發現了吧，用反覆運算代碼來實現基本是毫秒級的，而用遞迴來實現就考驗你的CPU能力啦（N秒～N分鐘不等）。這就是小甲魚不支持大家所有東西都用遞迴求解的原因，本來好好的一個代碼，給你用了遞迴，效率反而拉下了一大截。
為了體現遞迴正確使用的優勢，下一節我們來談談利用遞迴解決漢諾塔難題。如果你不懂得遞迴，試圖想要寫個程式來解決問題是相當困難的，但如果使用了遞迴，你會發現問題奇跡般的變簡單了！
這裡可以線上玩這個遊戲，大家不妨邊玩邊思考代碼該怎麼實現：http://www.kaixin001.com/flashgame/game/10406.html。
6.6.4 漢諾塔
看過小甲魚其他教程的“魚油”們可能會說，怎麼一談到遞迴演算法就要拿漢諾塔來舉例呢？沒辦法，因為小甲魚小時候太笨了，這個遊戲老是玩不過關，好不容易在自學程式設計的時候，也卡在這裡好長一段時間，所以呢，現在懂了啊，可以得瑟了嘛！
漢諾塔（如圖6-9所示）的來源據說是這樣的：一位法國數學家曾編寫過一個印度的古老傳說：說的是，在世界中心貝拿勒斯的聖廟裡邊，有一塊黃銅板，上邊插著三根寶針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。然後不論白天或者黑夜，總有一個僧侶在按照下面的法則來移動這些金片：“一次只移動一片，不管在哪根針上，小片必須在大片上面。”規則很簡單，另外僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。
圖6-9 漢諾塔
要解決一個問題，大家說什麼最重要？沒錯，思路！思路有了，問題就可以隨之迎刃而解。遊戲上節課我們也玩了，小甲魚可不是讓大家白玩的，玩過之後大家心裡有底，現在的分析大家才容易聽進去。
對於遊戲的玩法，可以簡單分解為三個步驟：
（1）將前63個盤子從X移動到Y上，確保大盤在小盤下。
（2）將最底下的第64個盤子從X移動到Z上。
（3）將Y上的63個盤子移動到Z上。
這樣看上去問題就簡單一點了，有些魚油說小甲魚你這不廢話嘛！？有說跟沒說一樣！因為關鍵在於步驟（1）和步驟（3）應該如何執行才是讓人頭疼的問題。
但是你仔細思考下，在遊戲中，我們發現由於每次只能移動一個圓盤，所以在移動的過程中顯然要借助另外一根針才可以實施。也就是說，步驟（1）將1～63個盤子需要借助Z移到Y上，步驟（3）將Y針上的63個盤子需要借助X移到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上。
說到這裡，是不是發現了什麼？沒錯，漢諾塔的拆解過程剛好滿足遞迴演算法的定義，因此，對於如此難題，使用遞迴來解決，問題就變得相當的簡單。參考代碼：
看，這就是遞迴的魔力！
0 留言:
發佈留言