你好，遞回！

http://wiki.jikexueyuan.com/project/haskell-guide/images/recursion.png" alt="" />

前面的章節(jié)中我們簡(jiǎn)要談了一下遞回。而在本章，我們會(huì)深入地了解到它為何在 Haskell 中是如此重要，能夠以遞回思想寫(xiě)出簡(jiǎn)潔優(yōu)雅的程式碼。

如果你還不知道什么是遞回，就讀這個(gè)句子。哈哈！開(kāi)個(gè)玩笑而已！遞回實(shí)際上是定義函數(shù)以呼叫自身的方式。在數(shù)學(xué)定義中，遞回隨處可見(jiàn)，如斐波那契數(shù)列 （fibonacci）。它先是定義兩個(gè)非遞回的數(shù)：F(0)=0,F(1)=1，表示斐波那契數(shù)列的前兩個(gè)數(shù)為 0 和 1。然后就是對(duì)其他自然數(shù)，其斐波那契數(shù)就是它前面兩個(gè)數(shù)字的和，即 F(N)=F(N-1)+F(N-2)。這樣一來(lái)，F(3) 就是 F(2)+F(1)，進(jìn)一步便是 (F(1)+F(0))+F(1)。已經(jīng)下探到了前面定義的非遞回斐波那契數(shù)，可以放心地說(shuō) F(3) 就是 2 了。在遞回定義中聲明的一兩個(gè)非遞回的值（如 F(0) 和 F(1)） 也可以稱(chēng)作邊界條件，這對(duì)遞回函數(shù)的正確求值至關(guān)重要。要是前面沒(méi)有定義 F(0) 和 F(1) 的話，它下探到 0 之后就會(huì)進(jìn)一步到負(fù)數(shù)，你就永遠(yuǎn)都得不到結(jié)果了。一不留神它就算到了 F(-2000)=F(-2001)+F(-2002)，并且永遠(yuǎn)都算不到頭！

遞回在 Haskell 中非常重要。命令式語(yǔ)言要求你提供求解的步驟，Haskell 則傾向于讓你提供問(wèn)題的描述。這便是 Haskell 沒(méi)有 while 或 for 循環(huán)的原因，遞回是我們的替代方案。

實(shí)作 Maximum

maximum 函數(shù)取一組可排序的 List（屬于 Ord Typeclass） 做參數(shù)，并回傳其中的最大值。想想，在命令式風(fēng)格中這一函數(shù)該怎么實(shí)現(xiàn)。很可能你會(huì)設(shè)一個(gè)變數(shù)來(lái)存儲(chǔ)當(dāng)前的最大值，然后用循環(huán)遍歷該 List，若存在比這個(gè)值更大的元素，則修改變數(shù)為這一元素的值。到最后，變數(shù)的值就是運(yùn)算結(jié)果。唔！描述如此簡(jiǎn)單的算法還頗費(fèi)了點(diǎn)口舌呢！

現(xiàn)在看看遞回的思路是如何：我們先定下一個(gè)邊界條件，即處理單個(gè)元素的 List 時(shí)，回傳該元素。如果該 List 的頭部大于尾部的最大值，我們就可以假定較長(zhǎng)的 List 的最大值就是它的頭部。而尾部若存在比它更大的元素，它就是尾部的最大值。就這么簡(jiǎn)單！現(xiàn)在，我們?cè)?Haskell 中實(shí)現(xiàn)它

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

如你所見(jiàn)，模式匹配與遞回簡(jiǎn)直就是天造地設(shè)！大多數(shù)命令式語(yǔ)言中都沒(méi)有模式匹配，于是你就得造一堆 if-else 來(lái)測(cè)試邊界條件。而在這里，我們僅需要使用模式將其表示出來(lái)。第一個(gè)模式說(shuō)，如果該 List 為空，崩潰！就該這樣，一個(gè)空 List 的最大值能是啥？我不知道。第二個(gè)模式也表示一個(gè)邊緣條件，它說(shuō)， 如果這個(gè) List 僅包含單個(gè)元素，就回傳該元素的值。

現(xiàn)在是第三個(gè)模式，執(zhí)行動(dòng)作的地方。 通過(guò)模式匹配，可以取得一個(gè) List 的頭部和尾部。這在使用遞回處理 List 時(shí)是十分常見(jiàn)的。出于習(xí)慣，我們用個(gè) where 語(yǔ)句來(lái)表示 maxTail 作為該 List 中尾部的最大值，然后檢查頭部是否大于尾部的最大值。若是，回傳頭部；若非，回傳尾部的最大值。

我們?nèi)€(gè) List [2,5,1] 做例子來(lái)看看它的工作原理。當(dāng)呼叫 maximum' 處理它時(shí)，前兩個(gè)模式不會(huì)被匹配，而第三個(gè)模式匹配了它并將其分為 2 與 [5,1]。 where 子句再取 [5,1] 的最大值。于是再次與第三個(gè)模式匹配，并將 [5,1] 分割為 5 和 [1]。繼續(xù)，where 子句取 [1] 的最大值，這時(shí)終于到了邊緣條件！回傳 1。進(jìn)一步，將 5 與 [1] 中的最大值做比較，易得 5，現(xiàn)在我們就得到了 [5,1] 的最大值。再進(jìn)一步，將 2 與 [5,1] 中的最大值相比較，可得 5 更大，最終得 5。

改用 max 函數(shù)會(huì)使程式碼更加清晰。如果你還記得，max 函數(shù)取兩個(gè)值做參數(shù)并回傳其中較大的值。如下便是用 max 函數(shù)重寫(xiě)的 maximun'

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs) = max x (maximum' xs)  

太漂亮了！一個(gè) List 的最大值就是它的首個(gè)元素與它尾部中最大值相比較所得的結(jié)果，簡(jiǎn)明扼要。

http://wiki.jikexueyuan.com/project/haskell-guide/images/maxs.png" alt="" />

來(lái)看幾個(gè)遞回函數(shù)

現(xiàn)在我們已經(jīng)了解了遞回的思路,接下來(lái)就使用遞回來(lái)實(shí)現(xiàn)幾個(gè)函數(shù). 先實(shí)現(xiàn)下 replicate 函數(shù), 它取一個(gè) Int 值和一個(gè)元素做參數(shù), 回傳一個(gè)包含多個(gè)重復(fù)元素的 List, 如 replicate 3 5 回傳 [5,5,5]. 考慮一下, 我覺(jué)得它的邊界條件應(yīng)該是負(fù)數(shù). 如果要 replicate 重復(fù)某元素零次, 那就是空 List. 負(fù)數(shù)也是同樣, 不靠譜.

replicate' :: (Num i, Ord i) => i -> a -> [a]  
replicate' n x  
    | n <= 0    = []  
    | otherwise = x:replicate' (n-1) x

在這里我們使用了 guard 而非模式匹配, 是因?yàn)檫@里做的是布林判斷. 如果 n 小于 0 就回傳一個(gè)空 List, 否則, 回傳以 x 作首個(gè)元素并后接重復(fù) n-1 次 x 的 List. 最后, (n-1) 的那部分就會(huì)令函數(shù)抵達(dá)邊緣條件.

*Note*: Num 不是 Ord 的子集, 表示數(shù)字不一定得拘泥于排序, 這就是在做加減法比較時(shí)要將 Num 與 Ord 型別約束區(qū)別開(kāi)來(lái)的原因.

接下來(lái)實(shí)現(xiàn) take 函數(shù), 它可以從一個(gè) List 取出一定數(shù)量的元素. 如 take 3 [5,4,3,2,1], 得 [5,4,3]. 若要取零或負(fù)數(shù)個(gè)的話就會(huì)得到一個(gè)空 List. 同樣, 若是從一個(gè)空 List中取值, 它會(huì)得到一個(gè)空 List. 注意, 這兒有兩個(gè)邊界條件, 寫(xiě)出來(lái):

take' :: (Num i, Ord i) => i -> [a] -> [a]  
take' n _  
    | n <= 0   = []  
take' _ []     = []  
take' n (x:xs) = x : take' (n-1) xs 

http://wiki.jikexueyuan.com/project/haskell-guide/images/painter.png" alt="" />

首個(gè)模式辨認(rèn)若為 0 或負(fù)數(shù), 回傳空 List. 同時(shí)注意這里用了一個(gè) guard 卻沒(méi)有指定 otherwise 部分, 這就表示 n 若大于 0, 會(huì)轉(zhuǎn)入下一模式. 第二個(gè)模式指明了若試圖從一個(gè)空 List 中取值, 則回傳空 List. 第三個(gè)模式將 List 分割為頭部和尾部, 然后表明從一個(gè) List 中取多個(gè)元素等同于令 x 作頭部后接從尾部取 n-1 個(gè)元素所得的 List. 假如我們要從 [4,3,2,1] 中取 3 個(gè)元素, 試著從紙上寫(xiě)出它的推導(dǎo)過(guò)程

reverse 函數(shù)簡(jiǎn)單地反轉(zhuǎn)一個(gè) List, 動(dòng)腦筋想一下它的邊界條件! 該怎樣呢? 想想...是空 List! 空 List 的反轉(zhuǎn)結(jié)果還是它自己. Okay, 接下來(lái)該怎么辦? 好的, 你猜的出來(lái). 若將一個(gè) List 分割為頭部與尾部, 那它反轉(zhuǎn)的結(jié)果就是反轉(zhuǎn)后的尾部與頭部相連所得的 List.

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]  

繼續(xù)下去!

Haskell 支持無(wú)限 List，所以我們的遞回就不必添加邊界條件。這樣一來(lái)，它可以對(duì)某值計(jì)算個(gè)沒(méi)完, 也可以產(chǎn)生一個(gè)無(wú)限的資料結(jié)構(gòu)，如無(wú)限 List。而無(wú)限 List 的好處就在于我們可以在任意位置將它斷開(kāi).

repeat 函數(shù)取一個(gè)元素作參數(shù), 回傳一個(gè)僅包含該元素的無(wú)限 List. 它的遞回實(shí)現(xiàn)簡(jiǎn)單的很, 看:

repeat' :: a -> [a]  
repeat' x = x:repeat' x  

呼叫 repeat 3 會(huì)得到一個(gè)以 3 為頭部并無(wú)限數(shù)量的 3 為尾部的 List, 可以說(shuō) repeat 3 運(yùn)行起來(lái)就是 3:repeat 3 , 然后 3:3:3:3 等等. 若執(zhí)行 repeat 3, 那它的運(yùn)算永遠(yuǎn)都不會(huì)停止。而 take 5 (repeat 3) 就可以得到 5 個(gè) 3, 與 replicate 5 3 差不多.

zip 取兩個(gè) List 作參數(shù)并將其捆在一起。zip [1,2,3] [2,3] 回傳 [(1,2),(2,3)], 它會(huì)把較長(zhǎng)的 List 從中間斷開(kāi), 以匹配較短的 List. 用 zip 處理一個(gè) List 與空 List 又會(huì)怎樣? 嗯, 會(huì)得一個(gè)空 List, 這便是我們的限制條件, 由于 zip 取兩個(gè)參數(shù), 所以要有兩個(gè)邊緣條件

zip' :: [a] -> [b] -> [(a,b)]  
zip' _ [] = []  
zip' [] _ = []  
zip' (x:xs) (y:ys) = (x,y):zip' xs ys  

前兩個(gè)模式表示兩個(gè) List 中若存在空 List, 則回傳空 List. 第三個(gè)模式表示將兩個(gè) List 捆綁的行為, 即將其頭部配對(duì)并后跟捆綁的尾部. 用 zip 處理 [1,2,3] 與 ['a','b'] 的話, 就會(huì)在 [3] 與 [] 時(shí)觸及邊界條件, 得到 (1,'a'):(2,'b'):[] 的結(jié)果,與 [(1,'a'),(2,'b')] 等價(jià).

再實(shí)現(xiàn)一個(gè)標(biāo)準(zhǔn)庫(kù)函數(shù) -- elem! 它取一個(gè)元素與一個(gè) List 作參數(shù), 并檢測(cè)該元素是否包含于此 List. 而邊緣條件就與大多數(shù)情況相同, 空 List. 大家都知道空 List 中不包含任何元素, 便不必再做任何判斷

elem' :: (Eq a) => a -> [a] -> Bool  
elem' a [] = False  
elem' a (x:xs)  
    | a == x    = True  
    | otherwise = a `elem'` xs   

這很簡(jiǎn)單明了。若頭部不是該元素, 就檢測(cè)尾部, 若為空 List 就回傳 False.

"快速"排序

http://wiki.jikexueyuan.com/project/haskell-guide/images/quickman.png" alt="" />

假定我們有一個(gè)可排序的 List, 其中元素的型別為 Ord Typeclass 的成員. 現(xiàn)在我們要給它排序! 有個(gè)排序算法非常的酷, 就是快速排序 (quick sort), 睿智的排序方法. 盡管它在命令式語(yǔ)言中也不過(guò) 10 行, 但在 Haskell 下邊要更短, 更漂亮, 儼然已經(jīng)成了 Haskell 的招牌了. 嗯, 我們?cè)谶@里也實(shí)現(xiàn)一下. 或許會(huì)顯得很俗氣, 因?yàn)槊總€(gè)人都用它來(lái)展示 Haskell 究竟有多優(yōu)雅!

它的型別聲明應(yīng)為 quicksort :: (Ord a) => [a] -> [a], 沒(méi)啥奇怪的. 邊界條件呢? 如料，空 List。排過(guò)序的空 List 還是空 List。接下來(lái)便是算法的定義：排過(guò)序的 List 就是令所有小于等于頭部的元素在先(它們已經(jīng)排過(guò)了序), 后跟大于頭部的元素(它們同樣已經(jīng)拍過(guò)了序)。 注意定義中有兩次排序，所以就得遞回兩次！同時(shí)也需要注意算法定義的動(dòng)詞為"是"什么而非"做"這個(gè), "做"那個(gè), 再"做"那個(gè)...這便是函數(shù)式編程之美！如何才能從 List 中取得比頭部小的那些元素呢？List Comprehension。好，動(dòng)手寫(xiě)出這個(gè)函數(shù)！

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  

小小的測(cè)試一下, 看看結(jié)果是否正確~

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! 如我所說(shuō)的一樣! 若給 [5,1,9,4,6,7,3] 排序，這個(gè)算法就會(huì)取出它的頭部，即 5。 將其置于分別比它大和比它小的兩個(gè) List 中間，得 [1,4,3] ++ [5] ++ [9,6,7], 我們便知道了當(dāng)排序結(jié)束之時(shí)，5會(huì)在第四位，因?yàn)橛?個(gè)數(shù)比它小每，也有三個(gè)數(shù)比它大。好的，接著排 [1,4,3] 與 [9,6,7], 結(jié)果就出來(lái)了！對(duì)它們的排序也是使用同樣的函數(shù)，將它們分成許多小塊，最終到達(dá)臨界條件，即空 List 經(jīng)排序依然為空，有個(gè)插圖：

橙色的部分表示已定位并不再移動(dòng)的元素。從左到右看，便是一個(gè)排過(guò)序的 List。在這里我們將所有元素與 head 作比較，而實(shí)際上就快速排序算法而言，選擇任意元素都是可以的。被選擇的元素就被稱(chēng)作錨 （pivot），以方便模式匹配。小于錨的元素都在淺綠的部分，大于錨都在深綠部分，這個(gè)黃黃的坡就表示了快速排序的執(zhí)行方式：

http://wiki.jikexueyuan.com/project/haskell-guide/images/quicksort.png" alt="" />

用遞回來(lái)思考

我們已經(jīng)寫(xiě)了不少遞回了，也許你已經(jīng)發(fā)覺(jué)了其中的固定模式：先定義一個(gè)邊界條件，再定義個(gè)函數(shù)，讓它從一堆元素中取一個(gè)并做點(diǎn)事情后，把余下的元素重新交給這個(gè)函數(shù)。 這一模式對(duì) List、Tree 等資料結(jié)構(gòu)都是適用的。例如，sum 函數(shù)就是一個(gè) List 頭部與其尾部的 sum 的和。一個(gè) List 的積便是該 List 的頭與其尾部的積相乘的積，一個(gè) List 的長(zhǎng)度就是 1 與其尾部長(zhǎng)度的和. 等等

http://wiki.jikexueyuan.com/project/haskell-guide/images/brain.png" alt="" />

再者就是邊界條件。一般而言，邊界條件就是為避免程序出錯(cuò)而設(shè)置的保護(hù)措施，處理 List 時(shí)的邊界條件大部分都是空 List，而處理 Tree 時(shí)的邊界條件就是沒(méi)有子元素的節(jié)點(diǎn)。

處理數(shù)字時(shí)也與之相似。函數(shù)一般都得接受一個(gè)值并修改它。早些時(shí)候我們編寫(xiě)過(guò)一個(gè)計(jì)算 Fibonacci 的函數(shù)，它便是某數(shù)與它減一的 Fibonacci 數(shù)的積。讓它乘以零就不行了， Fibonacci 數(shù)又都是非負(fù)數(shù)，邊界條件便可以定為 1，即乘法的單位元。 因?yàn)槿魏螖?shù)乘以 1 的結(jié)果還是這個(gè)數(shù)。而在 sum 中，加法的單位元就是 0。在快速排序中，邊界條件和單位元都是空 List，因?yàn)槿我?List 與空 List 相加的結(jié)果依然是原 List。

使用遞回來(lái)解決問(wèn)題時(shí)應(yīng)當(dāng)先考慮遞回會(huì)在什么樣的條件下不可用, 然后再找出它的邊界條件和單位元, 考慮參數(shù)應(yīng)該在何時(shí)切開(kāi)(如對(duì) List 使用模式匹配), 以及在何處執(zhí)行遞回.