Haskell递归的基本概念和列表上的递归

Haskell递归的基本概念和列表上的递归

什么是递归？递归函数是调用自身的函数。
那么这是递归的吗？
f x = f x
嗯，是的，但它并不是真的有用。
这是一个完全有效的函数定义,它是无限递归的
为了有用，递归函数必须有一个基本案例（告诉它何时停止递归）,递归到那个基本情况（这样我们最终可以得到答案）

“必要”和“必要且充分”之间是有区别的
很多问题自然可以用递归的形式表达出来。 例如:
数的阶乘:
𝑛!=𝑛 𝑥 (𝑛−1) 𝑥 (𝑛−2) 𝑥 …𝑥 1
阶乘的递归定义：

所以我可以类似地编写 Haskell 解决方案

列表中的递归
尽管有许多数字问题可以递归解决，但列表可能是您最常使用递归的地方。
您将使用的一般模式是：
在列表中的第一项中执行某些操作，然后递归列表的其余部分，直到列表中没有任何内容
例如:
len :: [a] -> Int
len [] = 0
length (x:xs) = 1 + length xs

递归的一般方法
从类型定义开始;接下来，停止条件（基本情况）是什么？最后，什么是递归案例？
工作示例：成员,即定义一个函数成员，如果项目在列表中，则返回 true，否则返回 false

“Eq t”表示 t 可以是任何可以进行等价测试的类型
此函数与现有库函数执行相同的操作：elem

示例：斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

示例: 查找列表中的第 n 个项目

这重复了 !! 操作

示例: 创建两个集合的并集，其中一个集合由一个列表描述（并且一个集合只有一个任何元素的实例）

示例: 编写一个函数 subst 将列表中的所有 𝑥 实例替换为 𝑦

示例: 找到两个集合的交集，其中集合像以前一样表示为列表

今天我们介绍了：递归的基础。
特别是，为了有用，递归函数必须有一个基本案例（告诉它何时停止递归）递归到那个基本情况（这样我们最终可以得到答案）和Haskell 中递归定义的一般方法