[TOC] ## 你好，遞歸！  前面的章節中我們簡要談了一下遞歸。而在本章，我們會深入地了解到它為何在haskell中是如此重要，能夠以遞歸思想寫出簡潔優雅的代碼。 如果你還不明白什么是遞歸，就讀這個句子。哈哈！玩笑而已！遞歸實際上是定義函數以調用自身的方式。在數學定義中，遞歸隨處可見，如斐波那契數列（fibonacci）。它先是定義兩個非遞歸的數：_F(0)=0,F(1)=1_，表示斐波那契數列的前兩個數為0和 1。然后就是對其他自然數，其斐波那契數就是它前面兩個數字的和，即_F(N)=F(N-1)+F(N-2)_。這樣一來，_F(3)_就是_F(2)+F(1)_，進一步便是_(F(1)+F(0))+F(1)_。已經下探到了前面定義的非遞歸斐波那契數，可以放心地說_F(3)_就是2了。在遞歸定義中聲明的一兩個非遞歸的值（如_F(0)_和_F(1)_）也可以稱作**邊界條件**，這對遞歸函數的正確求值至關重要。要是前面沒有定義_F(0)_和_F(1)_的話，它下探到0之后就會進一步到負數，你就永遠都得不到結果了。一不留神它就算到了_F(-2000)=F(-2001)+F(-2002)_，并且永遠都算不到頭！ 遞歸在haskell中至關重要。命令式語言要求你提供求解的步驟，haskell則傾向于讓你提供問題的描述。這便是haskell沒有while或for循環的原因，遞歸是我們的替代方案。 ## 麥克西米不可思議 `maximum`函數取一組可排序的List（屬于 Ord類型類）做參數，并返回其中的最大值。想想，在命令式風格中這一函數該怎么實現。很可能你會設一個變量來存儲當前的最大值，然后用循環遍歷該 List，若存在比這個值更大的元素，則修改變量為這一元素的值。到最后，變量的值就是運算結果。唔！描述如此簡單的算法還頗費了點口舌呢！ 現在看看遞歸的思路是如何：我們先定下一個邊緣條件，即處理單個元素的List時，返回該元素。如果該List的頭部大于尾部的最大值，我們就可以假定較長 的List的最大值就是它的頭部。而尾部若存在比它更大的元素，它就是尾部的最大值。就這么簡單！現在，我們在haskell中實現它 ~~~ maximum'?::?(Ord?a)?=>?[a]?->?a??? maximum'?[]?=?error?"maximum?of?empty?list"??? maximum'?[x]?=?x??? maximum'?(x:xs)???? ????|?x?>?maxTail?=?x??? ????|?otherwise?=?maxTail??? ????where?maxTail?=?maximum'?xs ~~~ 如你所見，模式匹配與遞歸簡直就是天造地設！大多數命令式語言中都沒有模式匹配，于是你就得造一堆if-else來測試邊界條件。而在這里，我們僅需要使用 模式將其表示出來。第一個模式說，如果該List為空，崩潰！就該這樣，一個空List的最大值能是啥？我不知道。第二個模式也表示一個邊緣條件，它說， 如果這個List僅包含單個元素，就返回該元素的值。 現在是第三個模式，執行動作的地方。 通過模式匹配，可以取得一個List的頭部和尾部。這在使用遞歸處理List時是十分常見的。出于習慣，我們用個where語句來表示`maxTail`作為該List中尾部的最大值，然后檢查頭部是否大于尾部的最大值。若是，返回頭部；若非，返回尾部的最大值。 我們取個List`[2,5,1]`做例子來看看它的工作原理。當調用`maximum'`處理它時，前兩個模式不會被匹配，而第三個模式匹配了它并將其分為`2`與`[5,1]`。 where子句再取`[5,1]`的最大值。于是再次與第三個模式匹配，并將`[5,1]`分割為`5`和`[1]`。繼續，where子句取`[1]`的最大值，這時終于到了邊緣條件！返回`1`。進一步，將`5`與`[1]`中的最大值做比較，易得5，現在我們就得到了`[5,1]`的最大值。再進一步，將`2`與`[5,1]`中的最大值相比較，可得`5`更大，最終得`5`。 改用`max`函數會使代碼更加清晰。如果你還記得，`max`函數取兩個值做參數并返回其中較大的值。如下便是用`max`函數重寫的`maximun'` ~~~ maximum'?::?(Ord?a)?=>?[a]?->?a??? maximum'?[]?=?error?"maximum?of?empty?list"??? maximum'?[x]?=?x??? maximum'?(x:xs)?=?max?x?(maximum'?xs) ~~~ 太漂亮了！一個List的最大值就是它的首個元素與它尾部中最大值相比較所得的結果，簡明扼要。  ## 幾個遞歸函數 現在我們已經了解了遞歸的思路,接下來就使用遞歸來實現幾個函數. 先實現下`replicate`函數, 它取一個`Int`值和一個元素做參數, 返回一個包含多個重復元素的List, 如`replicate 3 5`返回`[5,5,5]`. 考慮一下, 我覺得它的邊界條件應該是負數. 如果要replicate重復某元素零次, 那就是空List. 負數也是同樣, 不靠譜. ~~~ replicate'?::?(Num?i,?Ord?i)?=>?i?->?a?->?[a]??? replicate'?n?x??? ????|?n??0????=?[]??? ????|?otherwise?=?x:replicate'?(n-1)?x ~~~ 在這里我們使用了門衛而非模式匹配, 是因為這里做的是布爾判斷. 如果n小于0就返回一個空List, 否則, 返回以x作首個元素并后接重復n-1次x的List. 最后, (n-1)的那部分就會令函數抵達邊緣條件. > **Note**: Num不是Ord的子集, 表示數字不一定得拘泥于排序, 這就是在做加減法比較時要將Num與Ord類型約束區別開來的原因. 接下來實現`take`函數, 它可以從一個List取出一定數量的元素. 如`take 3 [5,4,3,2,1]`,得`[5,4,3]`. 若要取零或負數個的話就會得到一個空List. 同樣, 若是從一個空List中取值, 它會得到一個空List. 注意, 這兒有兩個邊界條件, 寫出來: ~~~ take'?::?(Num?i,?Ord?i)?=>?i?->?[a]?->?[a]??? take'?n?_??? ????|?n??0???=?[]??? take'?_?[]?????=?[]??? take'?n?(x:xs)?=?x?:?take'?(n-1)?xs ~~~  首個模式辨認若為0或負數, 返回空List. 同時注意這里用了一個門衛卻沒有指定otherwise部分, 這就表示n若大于0, 會轉入下一模式. 第二個模式指明了若試圖從一個空List中取值, 則返回空List. 第三個模式將List分割為頭部和尾部, 然后表明從一個list中取多個元素等同于令x作頭部后接從尾部取n-1個元素所得的List. 假如我們要從`[4,3,2,1]`中取3個元素, 試著從紙上寫出它的推導過程 `reverse`函數簡單地反轉一個List, 動腦筋想一下它的邊界條件! 該怎樣呢? 想想...是空List! 空List的反轉結果還是它自己. Okay , 接下來該怎么辦? 好的, 你猜的出來. 若將一個List分割為頭部與尾部, 那它反轉的結果就是反轉后的尾部與頭部相連所得的List. ~~~ reverse'?::?[a]?->?[a]??? reverse'?[]?=?[]??? reverse'?(x:xs)?=?reverse'?xs?++?[x] ~~~ 繼續進發! haskell支持無限List，所以我們的遞歸就不必添加邊界條件。這樣一來，它可以對某值計算個沒完, 也可以產生一個無限的數據結構，如無限List。而無限List的好處就在于我們可以在任意位置將它斷開. `repeat`函數取一個元素作參數, 返回一個僅包含該元素的無限List. 它的遞歸實現簡單的很, 看: ~~~ repeat'?::?a?->?[a]??? repeat'?x?=?x:repeat'?x ~~~ 調用`repeat 3`會得到一個以3為頭部并無限數量的3為尾部的List, 可以說`repeat 3`運行起來就是`3:repeat 3`, 然后`3:3:3:3`等等. 若執行`repeat 3`, 那它的運算永遠都不會停止。而`take 5 (repeat 3)`就可以得到5個3, 與`replicate 5 3`差不多. zip取兩個List作參數并將其捆在一起。`zip [1,2,3] [2,3]`返回`[(1,2),(2,3)]`, 它會把較長的List從中間斷開, 以匹配較短的List. 用zip處理一個List與空List又會怎樣? 嗯, 會得一個空List, 這便是我們的限制條件, 由于zip取兩個參數, 所以要有兩個邊緣條件 ~~~ zip'?::?[a]?->?[b]?->?[(a,b)]??? zip'?_?[]?=?[]??? zip'?[]?_?=?[]??? zip'?(x:xs)?(y:ys)?=?(x,y):zip'?xs?ys ~~~ 前兩個模式表示兩個List中若存在空List, 則返回空List. 第三個模式表示將兩個List捆綁的行為, 即將其頭部配對并后跟捆綁的尾部. 用zip處理`[1,2,3]`與`['a','b']`的話, 就會在`[3]`與`[]`時觸及邊界條件, 得到`(1,'a'):(2,'b'):[]`的結果,與`[(1,'a'),(2,'b')]`等價. 再實現一個標準庫函數--elem! 它取一個元素與一個List作參數, 并檢測該元素是否包含于此List. 而邊緣條件就與大多數情況相同, 空List. 大家都知道空List中不包含任何元素, 便不必再做任何判斷 ~~~ elem'?::?(Eq?a)?=>?a?->?[a]?->?Bool??? elem'?a?[]?=?False??? elem'?a?(x:xs)??? ????|?a?==?x????=?True??? ????|?otherwise?=?a?`elem'`?xs ~~~ 簡單直接. 若頭部不是該元素, 就檢測尾部, 若為空List就返回False ## 排序，要快！  假定我們有一個可排序的List,其中元素的類型為Ord類型類的成員. 現在我們要給它排序! 有個排序算法非常的酷, 就是快速排序(_quick sort_), 睿智的排序方法. 盡管它在命令式語言中也不過10行, 但在haskell下邊要更短,更漂亮, 儼然已經成了haskell的招牌了. 嗯, 我們在這里也實現一下. 或許會顯得很俗氣, 因為每個人都用它來展示haskell究竟有多優雅! 它的類型聲明應為`quicksort :: (Ord a) => [a] -> [a]`, 沒啥奇怪的. 邊界條件呢? 如料，空List。排過序的空List還是空List。接下來便是算法的定義：**排過序的List就是令所有小于等于頭部的元素在先(它們已經排過了序), 后跟大于頭部的元素(它們同樣已經拍過了序)**。 注意定義中有兩次排序，所以就得遞歸兩次！同時也需要注意算法定義的動詞為"是"什么而非"做"這個,"做"那個,再"做"那個...這便是函數式編程之美！如何才能從List中取得比頭部小的那些元素呢？List Comprehension。好，動手寫出這個函數！ ~~~ quicksort?::?(Ord?a)?=>?[a]?->?[a]??? quicksort?[]?=?[]??? quicksort?(x:xs)?=??? ??let?smallerSorted?=?quicksort?[a?|?a??xs,?a??x]?? ???????biggerSorted?=?quicksort?[a?|?a??xs,?a?>?x]??? ??in?smallerSorted?++?[x]?++?biggerSorted ~~~ 小小的測試一下, 看看結果是否正確~ ~~~ ghci>?quicksort?[10,2,5,3,1,6,7,4,2,3,4,8,9]??? [1,2,2,3,3,4,4,5,6,7,8,9,10]??? ghci>?quicksort?"the?quick?brown?fox?jumps?over?the?lazy?dog"??? "?abcdeeefghhijklmnoooopqrrsttuuvwxyz" ~~~ booyah! 如我所說的一樣! 若給`[5,1,9,4,6,7,3]`排序，這個算法就會取出它的頭部，即5。 將其至于分別比它大和比它小的兩個List中間，得`[1,4,3] ++ [5] ++ [9,6,7]`，我們便知道了當排序結束之時，5會在第四位，因為有3個數比它小每，也有三個數比它大。好的，接著排`[1,4,3]`與`[9,6,7]`，結果就出來了！對它們的排序也是使用同樣的函數，將它們分成許多小塊，最終到達臨界條件，即空List經排序依然為空，有個插圖： 橙色的部分表示已定位并不再移動的元素。從左到右看，便是一個排過序的List。在這里我們將所有元素與head作比較，而實際上就快速排序算法而言，選擇任意元素都是可以的。被選擇的元素就被稱作錨（_pivot_），以方便模式匹配。小于錨的元素都在淺綠的部分，大于錨都在深綠部分，這個黃黃的坡就表示了快速排序的執行方式：  ## 遞歸地思考 我們已經遞不少歸了，也許你已經發覺了其中的固定模式：先定義一個邊界條件，再定義個函數，讓它從一堆元素中取一個并做點事情后，把余下的元素重新交給這個函數。 這一模式對List、Tree等數據結構都是適用的。例如，sum函數就是一個List頭部與其尾部的sum的和。一個List的積便是該List的頭與其尾部的積相乘的積，一個List的長度就是1與其尾部長度的和. 等等  再者就是邊界條件。一般而言，邊界條件就是為避免程序出錯而設置的保護措施，處理List時的邊界條件大部分都是空List，而處理Tree時的邊界條件就是沒有子元素的節點。 處理數字時也與之相似。函數一般都得接受一個值并修改它。早些時候我們編寫過一個計算斐波納契的函數，它便是某數與它減一的斐波納契數的積。讓它乘以零就不行了， 斐波納契數又都是非負數，邊界條件便可以定為1，即乘法的單位元。 因為任何數乘以1的結果還是這個數。而在sum中，加法的單位元就是0。在快速排序中，邊界條件和單位元都是空List，因為任一List與空List相加的結果依然是原List。 使用遞歸來解決問題時應當先考慮遞歸會在什么樣的條件下不可用, 然后再找出它的邊界條件和單位元, 考慮參數應該在何時切開(如對List使用模式匹配), 以及在何處執行遞歸.