第 6 章：递归函数（Recursive functions）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 6。维护者已确认本书可翻译并发布用于学习研究。
本章介绍递归，这是 Haskell 中实现循环的基本机制。我们先从整数上的递归开始，然后把这个思想扩展到列表上的递归，接着讨论多个参数、多重递归和相互递归，最后给出一些定义递归函数的建议。
6.1 基本概念（Basic concepts）
正如前几章所见，许多函数都可以自然地根据其他函数来定义。例如，一个返回非负整数阶乘的函数，可以通过库函数计算从一到给定数字之间所有整数的乘积来定义：
fac :: Int -> Int
fac n = product [1..n]
在 Haskell 中，也允许根据函数自身来定义函数；这种函数称为递归函数。例如，阶乘函数可以用这种方式定义如下：
fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n-1)
第一个方程说明零的阶乘为一，称为基本情况（base case）。第二个方程说明任意其他数字的阶乘等于该数字与其前驱数字的阶乘之积，称为递归情况（recursive case）。例如，下面的计算展示了如何使用这个定义计算三的阶乘：
fac 3
= { applying fac }
3 * fac 2
= { applying fac }
3 * (2 * fac 1)
= { applying fac }
3 * (2 * (1 * fac 0))
= { applying fac }
3 * (2 * (1 * 1))
= { applying * }
6
注意，虽然函数 fac 是根据自身定义的，但它不会永远循环。具体来说，fac 的每次应用都会把非负整数参数减一，直到最终到达零；此时递归停止，并执行乘法。把零的阶乘定义为一是合适的，因为一是乘法的单位元。也就是说，对于任意整数 x，都有 1 * x = x 且 x * 1 = x。
对于阶乘函数来说，最初使用库函数的定义比使用递归的定义更简单。不过，正如本书后续将看到的，许多函数都有简单而自然的递归定义。例如，Haskell 中许多库函数就是这样定义的。此外，正如第 16 章将看到的，使用递归定义函数也使我们能够用归纳法这种简单但强大的技术证明这些函数的性质。
作为整数递归的另一个例子，考虑上面使用的乘法操作符 *。出于效率原因，这个操作符在 Haskell 中作为原语提供。不过，对于非负整数，它也可以通过对两个参数中的任意一个做递归来定义，例如对第二个参数递归：
(*) :: Int -> Int -> Int
m * 0 = 0
m * n = m + (m * (n-1))
例如：
4 * 3
= { applying * }
4 + (4 * 2)
= { applying * }
4 + (4 + (4 * 1))
= { applying * }
4 + (4 + (4 + (4 * 0)))
= { applying * }
4 + (4 + (4 + 0))
= { applying + }
12
也就是说，操作符 * 的递归定义形式化了这样一个思想：乘法可以化归为重复加法。
6.2 列表上的递归（Recursion on lists）
递归并不局限于作用于整数的函数，也可以用于定义作用于列表的函数。例如，前一节使用的库函数 product 可以定义如下：
product :: Num a => [a] -> a
product [] = 1
product (n:ns) = n * product ns
第一个方程说明数字空列表的乘积为一，这是合适的，因为一是乘法的单位元。第二个方程说明任意非空列表的乘积等于第一个数字与剩余列表乘积相乘。例如：
product [2,3,4]
= { applying product }
2 * product [3,4]
= { applying product }
2 * (3 * product [4])
= { applying product }
2 * (3 * (4 * product []))
= { applying product }
2 * (3 * (4 * 1))
= { applying * }
24
回顾一下，Haskell 中的列表实际上是使用 cons 操作符每次构造一个元素。因此，[2,3,4] 只是 2:(3:(4:[])) 的缩写。作为列表递归的另一个简单例子，库函数 length 可以使用与 product 相同的递归模式来定义：
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
也就是说，空列表的长度为零，而任意非空列表的长度是其尾部长度的后继。注意递归情况中使用了通配符模式 _，这反映了一个事实：计算列表长度并不依赖列表元素的值。
现在考虑反转列表的库函数。这个函数可以用递归定义如下：
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
也就是说，空列表的反转仍然是空列表，而任意非空列表的反转可以通过把其尾部的反转结果与由该列表头部组成的单元素列表连接起来得到。例如：
reverse [1,2,3]
= { applying reverse }
reverse [2,3] ++ [1]
= { applying reverse }
(reverse [3] ++ [2]) ++ [1]
= { applying reverse }
((reverse [] ++ [3]) ++ [2]) ++ [1]
= { applying reverse }
(([] ++ [3]) ++ [2]) ++ [1]
= { applying ++ }
[3,2,1]
而上面 reverse 定义中使用的连接操作符 ++，本身也可以通过对第一个参数递归来定义：
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
例如：
[1,2,3] ++ [4,5]
= { applying ++ }
1 : ([2,3] ++ [4,5])
= { applying ++ }
1 : (2 : ([3] ++ [4,5]))
= { applying ++ }
1 : (2 : (3 : ([] ++ [4,5])))
= { applying ++ }
1 : (2 : (3 : [4,5]))
= { list notation }
[1,2,3,4,5]
也就是说，++ 的递归定义形式化了这样一个思想：可以通过复制第一个列表中的元素来连接两个列表，直到第一个列表耗尽，此时再把第二个列表接到末尾。
本节最后给出两个关于有序列表递归的例子。首先，可以定义一个函数，把任意有序类型的新元素插入到一个有序列表中，并得到另一个有序列表：
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x <= y = x : y : ys
| otherwise = y : insert x ys
也就是说，把新元素插入空列表会得到一个单元素列表；而对于非空列表，结果取决于新元素 x 与列表头部 y 的顺序关系。具体来说，如果 x <= y，那么新元素 x 直接放到列表开头；否则，头部 y 成为结果列表的第一个元素，然后继续把新元素插入给定列表的尾部。例如：
insert 3 [1,2,4,5]
= { applying insert }
1 : insert 3 [2,4,5]
= { applying insert }
1 : 2 : insert 3 [4,5]
= { applying insert }
1 : 2 : 3 : [4,5]
= { list notation }
[1,2,3,4,5]
使用 insert 后，可以定义一个实现插入排序的函数。在插入排序中，空列表已经有序，而任意非空列表通过把其头部插入到其尾部排序后的结果中来排序：
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)
例如：
isort [3,2,1,4]
= { applying isort }
insert 3 (insert 2 (insert 1 (insert 4 [])))
= { applying insert }
insert 3 (insert 2 (insert 1 [4]))
= { applying insert }
insert 3 (insert 2 [1,4])
= { applying insert }
insert 3 [1,2,4]
= { applying insert }
[1,2,3,4]
6.3 多个参数（Multiple arguments）
带有多个参数的函数也可以通过同时对多个参数递归来定义。例如，库函数 zip 接收两个列表并产生一个二元组列表，它的定义如下：
zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
例如：
zip ['a','b','c'] [1,2,3,4]
= { applying zip }
('a',1) : zip ['b','c'] [2,3,4]
= { applying zip }
('a',1) : ('b',2) : zip ['c'] [3,4]
= { applying zip }
('a',1) : ('b',2) : ('c',3) : zip [] [4]
= { applying zip }
('a',1) : ('b',2) : ('c',3) : []
= { list notation }
[('a',1),('b',2),('c',3)]
注意，zip 的定义需要两个基本情况，因为两个参数列表中的任意一个都可能为空。作为多参数递归的另一个例子，库函数 drop 会从列表开头移除给定数量的元素，它的定义如下：
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
同样，这里需要两个基本情况：一个用于移除零个元素，另一个用于尝试从空列表中移除元素。
6.4 多重递归（Multiple recursion）
函数还可以使用多重递归来定义，也就是在函数自身的定义中多次应用该函数。例如，回忆 Fibonacci 序列 0,1,1,2,3,5,8,13,...，其中前两个数字是 0 和 1，而后续每个数字都是序列中前两个数字之和。可以使用双重递归定义一个函数，为任意整数 n >= 0 计算第 n 个 Fibonacci 数：
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)
作为另一个例子，第 1 章展示了如何实现另一种著名的列表排序方法，即快速排序：
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
where
smaller = [a | a <- xs, a <= x]
larger = [b | b <- xs, b > x]
也就是说，空列表已经有序，而任意非空列表都可以通过把其头部放在两个列表之间来排序。这两个列表分别来自对尾部中小于和大于头部的元素进行排序。
6.5 相互递归（Mutual recursion）
函数还可以使用相互递归来定义，也就是两个或多个函数都根据彼此递归定义。例如，考虑库函数 even 和 odd。出于效率原因，这两个函数通常使用除以二后的余数来定义。不过，对于非负整数，它们也可以使用相互递归来定义：
even :: Int -> Bool
even 0 = True
even n = odd (n-1)
odd :: Int -> Bool
odd 0 = False
odd n = even (n-1)
也就是说，零是偶数但不是奇数，而任意其他数字是否为偶数取决于它的前驱是否为奇数；是否为奇数则取决于它的前驱是否为偶数。例如：
even 4
= { applying even }
odd 3
= { applying odd }
even 2
= { applying even }
odd 1
= { applying odd }
even 0
= { applying even }
True
类似地，可以定义两个函数，分别选择列表中所有偶数位置和奇数位置（从零开始计数）的元素：
evens :: [a] -> [a]
evens [] = []
evens (x:xs) = x : odds xs
odds :: [a] -> [a]
odds [] = []
odds (_:xs) = evens xs
例如：
evens "abcde"
= { applying evens }
'a' : odds "bcde"
= { applying odds }
'a' : evens "cde"
= { applying evens }
'a' : 'c' : odds "de"
= { applying odds }
'a' : 'c' : evens "e"
= { applying evens }
'a' : 'c' : 'e' : odds []
= { applying odds }
'a' : 'c' : 'e' : []
= { string notation }
"ace"
回顾一下，Haskell 中的字符串实际上是作为字符列表构造出来的。因此，"abcde" 只是 ['a','b','c','d','e'] 的缩写。
6.6 关于递归的建议（Advice on recursion）
定义递归函数就像骑自行车：别人做起来看着很容易，第一次自己尝试时可能觉得不可能，但经过练习后会变得简单而自然。本节给出一些关于定义函数的一般建议，尤其是定义递归函数的建议。我们会通过三个例子介绍一个五步过程。
示例：product
作为第一个简单例子，我们展示如何以系统化的分步方式，构造本章前面给出的库函数 product 的定义，该函数用于计算数字列表的乘积。
步骤 1：定义类型
定义函数时，思考类型非常有帮助，因此在开始定义函数本身之前，先定义函数类型是一种好习惯。在这个例子中，我们从下面的类型开始：
product :: [Int] -> Int
它说明 product 接收一个整数列表，并产生单个整数。正如这个例子所示，从一个简单类型开始通常很有用，之后可以在过程中再细化或泛化它。
步骤 2：枚举情况
对于大多数参数类型，都有若干标准情况需要考虑。对于列表，标准情况是空列表和非空列表，因此可以使用模式匹配写出下面的骨架定义：
product [] =
product (n:ns) =
对于非负整数，标准情况是 0 和 n；对于逻辑值，标准情况是 False 和 True，依此类推。和类型一样，之后可能需要细化这些情况，但从标准情况开始很有用。
步骤 3：定义简单情况
根据定义，零个整数的乘积是一，因为一是乘法的单位元。因此，空列表情况很容易定义：
product [] = 1
product (n:ns) =
正如这个例子所示，简单情况通常会成为基本情况。
步骤 4：定义其他情况
如何计算非空整数列表的乘积？在这一步，先考虑可以使用的素材会很有帮助，例如函数自身（product）、参数（n 和 ns），以及具有相关类型的库函数（+、-、* 等）。在这个例子中，我们只需把第一个整数与剩余整数列表的乘积相乘：
product [] = 1
product (n:ns) = n * product ns
正如这个例子所示，其他情况通常会成为递归情况。
步骤 5：泛化并简化
一旦使用上述过程定义了函数，通常会发现它可以被泛化和简化。例如，函数 product 并不依赖应用对象的具体数字种类，因此它的类型可以从整数泛化为任意数字类型：
product :: Num a => [a] -> a
在简化方面，第 7 章会看到，product 中使用的递归模式由一个名为 foldr 的库函数封装。使用它后，product 可以用一个方程重新定义：
product = foldr (*) 1
因此，product 的最终定义如下：
product :: Num a => [a] -> a
product = foldr (*) 1
除了出于效率原因，标准 Prelude 中将 foldr 替换为相关函数 foldl 之外，这正是附录 B 中标准 Prelude 对列表给出的定义。foldl 也会在第 7 章讨论。
示例：drop
作为一个更实质的例子，现在展示如何使用五步过程，构造本章前面给出的库函数 drop 的定义，该函数从列表开头移除给定数量的元素。
步骤 1：定义类型
先从一个类型开始，它说明 drop 接收一个整数和一个由某种类型 a 的值组成的列表，并产生另一个由这类值组成的列表：
drop :: Int -> [a] -> [a]
注意，我们在定义这个类型时已经做出了四个设计决策：为了简单，使用整数而不是更一般的数字类型；为了灵活，使用柯里化而不是把参数作为二元组接收；为了可读性，把整数参数放在列表参数之前（形如 drop n xs 的表达式可以读作“从 xs 中丢弃 n 个元素”）；最后，为了通用性，让函数在列表元素类型上是多态的。
步骤 2：枚举情况
由于整数参数有两个标准情况（0 和 n），列表参数也有两个标准情况（[] 和 x:xs），使用模式匹配写出这个函数的骨架定义一共需要四种情况：
drop 0 [] =
drop 0 (x:xs) =
drop n [] =
drop n (x:xs) =
步骤 3：定义简单情况
根据定义，从任意列表开头移除零个元素会得到同一个列表，因此前两个情况很容易定义：
drop 0 [] = []
drop 0 (x:xs) = x:xs
drop n [] =
drop n (x:xs) =
尝试从空列表中移除一个或多个元素是无效的，因此第三个情况可以省略；如果这种情况出现，就会产生错误。不过在实践中，我们选择避免产生错误，而是在这种情况下返回空列表：
drop 0 [] = []
drop 0 (x:xs) = x:xs
drop n [] = []
drop n (x:xs) =
步骤 4：定义其他情况
如何从非空列表中移除一个或多个元素？只需从列表尾部移除少一个的元素即可：
drop 0 [] = []
drop 0 (x:xs) = x:xs
drop n [] = []
drop n (x:xs) = drop (n-1) xs
步骤 5：泛化并简化
由于函数 drop 不依赖应用对象的具体整数种类，它的类型可以泛化为任意整数类型，其中 Int 和 Integer 是标准实例：
drop :: Integral b => b -> [a] -> [a]
不过，正如 3.9 节所说，出于效率原因，标准 Prelude 实际上并未进行这种泛化。在简化方面，drop 的前两个方程可以合并为一个方程，说明从任意列表中移除零个元素会得到同一个列表：
drop 0 xs = xs
drop n [] = []
drop n (x:xs) = drop (n-1) xs
此外，第二个方程中的变量 n 和第三个方程中的变量 x 可以替换为通配符模式 _，因为这些变量没有在各自方程的主体中使用。因此，drop 的最终定义如下，这正是标准 Prelude 中的定义：
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
示例：init
作为最后一个例子，我们考虑如何构造库函数 init 的定义，该函数会移除非空列表的最后一个元素。
步骤 1：定义类型
先从一个类型开始，它说明 init 接收一个由某种类型 a 的值组成的列表，并产生另一个由这类值组成的列表：
init :: [a] -> [a]
步骤 2：枚举情况
由于空列表不是 init 的有效参数，使用模式匹配写出骨架定义只需要一种情况：
init (x:xs) =
步骤 3：定义简单情况
在前两个例子中，定义简单情况相当直接，但函数 init 需要多想一下。不过根据定义，从只有一个元素的列表中移除最后一个元素会得到空列表，因此可以引入守卫来处理这个简单情况：
init (x:xs) | null xs = []
| otherwise =
（库函数 null :: [a] -> Bool 判断列表是否为空。）
步骤 4：定义其他情况
如何从至少有两个元素的列表中移除最后一个元素？只需保留头部，并从尾部移除最后一个元素：
init (x:xs) | null xs = []
| otherwise = x : init xs
步骤 5：泛化并简化
init 的类型已经尽可能通用，但定义本身现在可以通过使用模式匹配而不是守卫来简化，并且在第一个方程中使用通配符模式而不是变量：
init :: [a] -> [a]
init [_] = []
init (x:xs) = x : init xs
这同样正是标准 Prelude 中的定义。
6.7 章注（Chapter remarks）
本章给出的递归定义强调清晰性，但其中许多定义都可以在效率或通用性方面改进，这一点会在本书后续内容中看到。定义函数的五步过程基于文献 [8]。
6.8 练习（Exercises）
- 如果把递归版阶乘函数应用到负参数，例如
(-1)，它会如何表现？通过给递归情况添加一个守卫来修改定义，禁止负参数。 - 定义递归函数
sumdown :: Int -> Int，返回从给定值向下到零的非负整数之和。例如，sumdown 3应返回结果3+2+1+0 = 6。 - 使用与乘法操作符
*相同的递归模式，为非负整数定义乘方操作符^，并展示表达式2 ^ 3如何使用你的定义求值。 - 定义递归函数
euclid :: Int -> Int -> Int，实现 Euclid 算法来计算两个非负整数的最大公约数：如果两个数字相等，这个数字就是结果；否则，从较大的数字中减去较小的数字，然后重复同样的过程。例如：
> euclid 6 27
3
-
使用本章给出的递归定义，展示
length [1,2,3]、drop 3 [1,2,3,4,5]和init [1,2,3]如何求值。 -
不查看标准 Prelude 中的定义，使用递归定义下面这些作用于列表的库函数。
a. 判断列表中的所有逻辑值是否都为
True：
and :: [Bool] -> Bool
b. 连接一个列表的列表：
concat :: [[a]] -> [a]
c. 产生包含 n 个相同元素的列表：
replicate :: Int -> a -> [a]
d. 选择列表的第 n 个元素：
(!!) :: [a] -> Int -> a
e. 判断某个值是否是列表中的元素：
elem :: Eq a => a -> [a] -> Bool
注意：这些函数大多在 Prelude 中使用其他库函数定义，而不是显式使用递归；它们也是泛型函数，而不是专门针对列表类型的函数。
- 定义递归函数
merge :: Ord a => [a] -> [a] -> [a]，把两个有序列表合并为一个有序列表。例如：
> merge [2,5,6] [1,3,4]
[1,2,3,4,5,6]
注意：你的定义不应使用其他作用于有序列表的函数，例如 insert 或 isort，而应使用显式递归定义。
- 使用
merge定义函数msort :: Ord a => [a] -> [a]，实现归并排序。在归并排序中，空列表和单元素列表已经有序，而其他任意列表都通过分别排序其两个半区，再把结果合并起来排序。
提示：先定义一个函数 halve :: [a] -> ([a],[a])，它把一个列表分成两半，两半长度最多相差一。
-
使用五步过程，构造下面这些库函数：
a. 计算数字列表的和； b. 从列表开头取给定数量的元素； c. 选择非空列表的最后一个元素。
练习 1-4 的解答见附录 A。