Haskell 基本语法（三）递归
source link: https://www.starky.ltd/2021/06/29/basic-haskell-recursion/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Haskell 基本语法（三）递归
递归是一种定义函数的方式，在该方式下，函数的定义中调用了该函数本身。有点像俄罗斯套娃。
数学中的定义很多时候都会用到递归，比如 fibonacci 数列：
F(0) = 1F(1) = 1F(n) = F(n - 1) + F(n - 2)
于是有 F(3) = F(2) + F(1) = (F(1) + F(0)) + F(1) = 2。
递归函数的定义中，并不只是包含调用自身的代码，常常还需要非递归形式的定义，如上面的 F(0) = 1 和 F(1) = 1。这样的代码称作边缘条件（edge condition）。
边缘条件对于递归函数的终止至关重要。假如上面的 F(0) 和 F(1) 未定义，则任何一个输入都会导致函数无限调用自身，永远不会终止。
递归是 Haskell 中很重要的概念。不同于命令式的语言，在 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
使用 max 函数（返回两个输入值中较大的那个）编写更短的形式：
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
当输入为 [2, 5, 1] 时，计算过程如下：maximum' [2, 5, 1] -> max 2 (maximum' [5, 1]) -> max 2 (max 5 (maximum' [1])) -> max 2 (max 5 1) -> max 2 5 -> 5。
生成由固定数量的同一元素构成的列表
replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
| n <= 0 = []
| otherwise = x:replicate' (n-1) x
如 replicate' 3 5 -> 5:(replicate' 2 5) -> 5:(5:(replicate' 1 5)) -> 5:(5:(5:(replicate' 0 5))) -> 5:(5:(5:[])) -> [5, 5, 5]。
取出列表中的前几个元素
take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs
其中 take' n _ 和 take' _ [] 分别作为两种不同情况下的终止条件。
第一个模式 take' n _ 表示当 n 小于等于 0 时，不管输入的是什么样的列表都返回空列表 []。
可以作为如 take' 2 [1, 2, 3] 的终止条件。即前两个元素被取出并拼接成 [1, 2] 后 n 等于 0，满足第一个模式，递归终止。
第二个模式 take _ [] 表示当输入的列表是空列表时，不管 n 是多少都返回空列表。
可以作为如 take' 3 [1, 2] 的终止条件。即前两个元素被取出并拼接成 [1, 2] 后，n 为 1，但列表成为空列表，满足第二个模式，递归终止。
第三个模式 take' n (x:xs) 则用来定义从输入的列表头部逐个取出 n 个元素并拼接成新列表的递归逻辑。
reverse 的自定义实现
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
zip 的自定义实现
zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys
elem 的自定义实现（判断某个元素是否属于某个列表）
elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
| a == x = True
| otherwise = a `elem'` xs
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
递归函数的定义通常遵循如下模式：
- 定义边缘条件（edge conditon）用于在特定条件下终止递归的执行
- 取出部分元素执行特定操作，再调用递归函数本身处理剩余的元素
某个列表中所有元素之和等于该列表的第一个元素加上剩余的所有元素之和；某个列表的长度等于尾部（去除头部第一个元素）所有元素的长度加 1。
通常情况下，edge condition 就是令递归函数无实际意义的条件。对于列表来说，最常见的 edge condition 就是空列表。
Recommend
-
54
这一系列是我学习 Learn You a Haskell For Great Good 之后，总结，编写的学习笔记。 这个系列主要分为五个部分：
-
60
这一系列是我学习 Learn You a Haskell For Great Good 之后，总结，编写的学习笔记。 这个系列主要分为五个部分：
-
25
变量的定义 /*使用var定义*/ //隐式初始值(初始化为零值) var num1 int var str2 string //显式初始值 var num2 int = 12 var str2 string = "xiaohei" //类型自动推断 var a, b, c = 3, 5, "xiaohei" /*:=方式声明变量*/ f, g...
-
34
前言： 647 目录如下： Go语言基础（一）—— 简介...
-
32
1 hello world 1.1 代码 package main import "fmt" func main() { fmt.Println("hello world") } 1.2 执行 // 方法1 编译并执行 go run ./test002.go // 方法2 先构建后...
-
46
C - @station - 本人是自学 C 语言结构体，文件操作( 位运算还没看 )这两天在复习，坐坐书上之前都没做的题下面是要学什么？ 如果有书请推荐下
-
19
本博客随笔主要记录本人学习过程中的知识，欢迎大家一同学习，有不对的地方很高兴读者能详细指出，感激不尽！ JVM内存结构 编译完源程序以后，生成一个或多个字节码文件。 我们使用JVM中的类的加...
-
10
Haskell 基本语法（二）模式匹配 发表于 2021-06-25 ...
-
3
Haskell 基本语法（四）高阶函数 发表于 2021-06-30 ...
-
5
Haskell 基本语法（五）自定义 Types 发表于 2021-07-06 ...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK