# 0. 你好，递归
递归（recursion）指在函数的定义中应用自身的方式。
一般倾向于将问题展开为同样的子问题，并不断对子问题进行展开和求解。
抵达问题的基准条件（base case）后，必须明确地给出一个非递归的结果。
命令式语言强调如何（how）进行计算，Haskell 则强调是什么（what）问题。
这正是递归发挥威力的地方，因此递归在 Haskell 中至关重要。
> 本章简单地介绍了一下递归，内容比较基础，本文以代码为主。
# 1. 不可思议的最大值
递归实现 `maximum` 函数：
```hs
maximum' :: Ord a => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x : xs) = max x (maximum' xs)
```
# 2. 更多的几个递归函数
## 2.1. `replicate`
递归实现 `replicate` 函数：
```hs
replicate' :: Int -> a -> [a]
replicate' n x
| n <= 0 = []
| otherwise = x : replicate' (n - 1) x
```
## 2.2. `take`
递归实现 `take` 函数：
```hs
take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x : xs) = x : take' (n - 1) xs
```
## 2.3. `reverse`
递归实现 `reverse` 函数：
```hs
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x : xs) = reverse' xs ++ [x]
```
## 2.4. `repeat`
递归实现 `repeat` 函数：
```hs
repeat' :: a -> [a]
repeat' x = x : repeat' x
```
## 2.5. `zip`
递归实现 `zip` 函数：
```hs
zip' :: [a] -> [b] -> [(a, b)]
zip' _ [] = []
zip' [] _ = []
zip' (x : xs) (y : ys) = (x, y) : zip' xs ys
```
## 2.6. `elem`
递归实现 `elem` 函数：
```hs
elem' :: Eq a => a -> [a] -> Bool
elem' _ [] = False
elem' a (x : xs)
| a == x = True
| otherwise = a `elem'` xs
```
# 3. 快点，排序！
快速排序（quick sort）算法通常是递归实现的。
下面简单地介绍一下最基本的快速排序算法。
## 3.1. 算法思路
1. 在待排序的列表中取一个元素作为基准（pivot）。
2. 将列表中不大于基准的元素安排在基准的左侧，其余元素安排在基准的右侧。
3. 递归地对基准的左侧和右侧进行排序即可。
## 3.2. 编写代码
```hs
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x : xs) =
let smallOrEqual = [a | a <- xs, a <= x]
larger = [a | a <- xs, a > x]
in quicksort smallOrEqual ++ [x] ++ quicksort larger
```
> 这里取列表的头部（第一个元素）作为基准，方便模式匹配。
测试一下：
```ghci
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"
```
# 4. 递归地思考
通过前面的代码可以总结出递归的一些固定模式。
使用递归解决问题，最好的方式是先确认基准条件，并把问题分解为几个相似的子问题。
一旦确定了正确的基准条件和子问题，接下来甚至都不需要对其余的细节多费心了。
只要确信子问题的正确性，然后根据子问题的求解结果组合成最终解即可。
《Haskell 趣学指南》学习笔记 - 第 4 章
