# 递归函数 Recursive Functions

## 基本概念​

There is also a video on this section.

fac :: Int -> Intfac n = product [1..n]

For example:

fac 5= product [1..5]= product [1,2,3,4,5]= 1*2*3*4*5= 120

fac :: Int -> Intfac 0 = 1fac n = n * fac (n-1)

For example:

fac 3= 3 * fac 2= 3 * (2 * fac 1)= 3 * (2 * (1 * fac 0))= 3 * (2 * (1 * 1))= 3 * (2 * 1)= 3 * 2= 6

Note:

• fac 0 = 1 is appropriate because 1 is the identity for multiplication: 1 x = x = x 1.

• 递归定义在整数<0 的情况下出现分歧，因为永远不会达到基数：

> fac (-1)*** Exception: stack overflow

### 递归为什么有用？ Why is Recursion Useful?​

• 有些函数，如阶乘，用其他函数来定义比较简单。

• 然而，正如我们将看到的那样，许多函数可以自然而然地以自身为单位进行定义。

• 使用递归定义的函数的属性可以用简单但强大的数学技术归纳法来证明。

## 列表上的递归 Recursion on Lists​

There is also a video on this section.

product' :: Num a => [a] -> aproduct' []     = 1product' (n:ns) = n * product' ns

product' 函数将空列表映射为 1（base case），任何非空列表映射为其头部乘以其尾部的 product'recursive case）。

For example:

product' [2,3,4]= 2 * product' [3,4]= 2 * (3 * product' [4])= 2 * (3 * (4 * product' []))= 2 * (3 * (4 * 1))= 24

length :: [a] -> Intlength []     = 0length (_:xs) = 1 + length xs

length 函数将空列表映射为 0（base case），将任何非空列表映射为其尾部长度的继承者（recursive case）。

For example:

length [1,2,3]= 1 + length [2,3]= 1 + (1 + length [3])= 1 + (1 + (1 + length []))= 1 + (1 + (1 + 0))= 3

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

For example:

reverse [1,2,3]= reverse [2,3] ++ [1]= (reverse [3] ++ [2]) ++ [1]= ((reverse [] ++ [3]) ++ [2]) ++ [1]= (([] ++ [3]) ++ [2]) ++ [1]= [3,2,1]

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

For example:

[1,2,3] ++ [4,5]= 1 : ([2,3] ++ [4,5])= 1 : (2 : ([3] ++ [4,5]))= 1 : (2 : (3 : ([] ++ [4,5])))= 1 : (2 : (3 : [4,5]))= [1,2,3,4,5]))

++ 的递归定义正式表明了这样一个观点：两个列表可以通过从第一个列表中复制元素来追加，直到它被耗尽，这时第二个列表就会被加入到最后。

## 多个论据 Multiple Arguments​

There is also a video on this section.

• 对两个列表的元素进行压缩：
zip :: [a] -> [b] -> [(a,b)]zip []     _      = []zip _      []     = []zip (x:xs) (y:ys) = (x,y) : zip xs ys

For example:

zip ['a', 'b', 'c'] [1,2,3,4]= ('a',1) : zip ['b', 'c'] [2,3,4]= ('a',1) : ('b',2) : zip ['c'] [3,4]= ('a',1) : ('b',2) : ('c',3) : zip [] [4]= ('a',1) : ('b',2) : ('c',3) : []= [('a',1), ('b',2), ('c',3)]
• 从一个列表中删除前 n 个元素：
drop :: Int -> [a] -> [a]drop 0 xs     = xsdrop _ []     = []drop n (_:xs) = drop (n-1) xs

For example:

drop 3 [4,6,8,10,12]= drop 2 [6,8,10,12]= drop 1 [8,10,12]= drop 0 [10,12][10,12]

## 多重递归 Multiple Recursion​

There is also a video on this section.

fib :: Int -> Intfib 0 = 0fib 1 = 1fib n = fib (n-2) + fib (n-1)

For example:

fib 4= fib (2) + fib (3)= fib (0) + fib (1) + fib (1) + fib (2)= 0 + 1 + 1 + fib (0) + fib (1)= 0 + 1 + 1 + 0 + 1= 3

## 相互递归 Mutual Recursion​

There is also a video on this section.

even :: Int -> Booleven 0 = Trueeven n = odd (n-1)odd :: Int -> Boolodd 0 = Falseodd n = even (n-1)

For example:

even 4= odd 3= even 2= odd 1= even 0= True

evens :: [a] -> [a]evens []     = []evens (x:xs) = x : odds xsodds :: [a] -> [a]odds []     = []odds (_:xs) = evens xs

For example:

evens "abcde"= 'a' : odds "bcde"= 'a' : evens "cde"= 'a' : 'c' : odds "de"= 'a' : 'c' : evens "e"= 'a' : 'c' : 'e' : odds []= 'a' : 'c' : 'e' : []= "ace"

## 编程实例 Programming Example - Quicksort​

There is also a video on this section.

• 空列表已经被排序

• 非空列表可以通过对尾部值 <= 头部进行排序，对尾部值 > 头部进行排序，然后将得到的列表附加在头部值的两侧。

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]

For example (abbreviating qsort as q):

## 关于递归的建议​

There is also a video on this section.

Example - drop: that removes a given number of elements from the start a list.

• Step 1: 定义类型

drop 函数接收一个整数和一个某种类型的值的列表 a，并产生另一个这种值的列表。

drop :: Int -> [a] -> [a]

(i) using integers rather than a more general numeric type - for simiplicity

(ii) using currying rather than taking arguments as a pair - for flexibility

(iii) supplying the integer argument before the list argument - for readability (drop n elements from xs)

(iv) making the function polymorphic in the type of the list elements - for generality.

• Step 2: enumerate the cases

drop 0 []     =drop 0 (x:xs) =drop n []     =drop n (x:xs) =
• Step 3: 定义简单的情况

drop 0 []     = []drop 0 (x:xs) = x:xsdrop n []     =drop n (x:xs) =

drop 0 []     = []drop 0 (x:xs) = x:xsdrop n []     = []drop n (x:xs) =
• Step 4: define the other cases

drop 0 []     = []drop 0 (x:xs) = x:xsdrop n []     = []drop n (x:xs) = drop (n-1) xs
• Step 5: 概括和简化

drop 0 xs     = xsdrop n []     = []drop n (x:xs) = drop (n-1) xs

drop :: Int -> [a] -> [a]drop 0 xs     = xsdrop _ []     = []drop n (_:xs) = drop (n-1) xs

## 练习​

(1) 不看标准序言，用递归定义以下库函数。

• 决定一个列表中的所有逻辑值是否为真：
and :: [Bool] -> Bool

and :: [Bool] -> Booland [] = Falseand (x:xs) = x && (and xs)
• 串联一个列表：
concat :: [[a]] -> [a]

concat :: [[a]] -> [a]concat [] = []concat (x:xs) = x ++ concat xs
• 生成一个有 n 个相同元素的列表：
replicate :: Int -> a -> [a]

replicate :: Int -> a -> [a]replicate n x | n <= 0 = []              | otherwise = x : replicate (n-1) x
• 选择一个列表中的第 n 个元素：
(!!) :: [a] -> Int -> a

(!!) :: [a] -> Int -> a(!!) [] _ = undefined(!!) (x:xs) n | n == 0 = x              | otherwise = (!!) xs (n-1)
• 决定一个值是否是一个列表的元素：
elem :: Eq a => a -> [a] -> Bool

elem :: Eq a => a -> [a] -> Boolelem n [] = Falseelem n (x:xs) | x == n = True              | otherwise = elem n xs

(2) 定义一个递归函数

merge :: Ord a => [a] -> [a] -> [a]

For example:

> merge [2,5,6] [1,3,4][1,2,3,4,5,6]

merge :: Ord a => [a] -> [a] -> [a]merge x [] = xmerge [] y = ymerge (x:xs) (y:ys) | x <= y = x:(merge xs (y:ys))                    | otherwise = y:(merge (x:xs) ys)