[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使用模式匹配), 以及在何处执行递归.