Recursion 入门

递归是指根据自身定义的东西。在编程环境中，它是使用自称函数或递归类型的实践。

递归函数

递归函数有两个部分：

• 一个或多个基本案例
• 递归步骤

因为递归函数调用自身，所以函数调用字符串可以永远继续。为了确保函数终止必须包含基本情况。这些将告诉函数何时返回值而不是执行另一个递归调用。通常，递归函数将检查它们对基本情况的输入，并在达到基本情况时返回。如果尚未到达基本情况，则该函数将进入递归步骤。

递归步骤是函数调用自身的时间。许多递归函数将返回对递归调用的结果执行的一些计算。Fibonacci 序列示例证明了这一点。该函数递归调用自身两次，然后返回这些调用的结果总和

递归的一个常见用途是在大型数据结构（例如树和图形）上导航和执行计算。这很有效，因为递归可以解决问题并解决较小的问题，并以解决更大问题的解决方案为基础。递归的另一个常见用途是在没有内置循环结构的语言（通常是函数语言）中执行迭代操作（循环）。

递归类型

递归类型的值是由相同类型的值组成的，或者表达方式不同：递归类型是根据自身定义的。例如，列表是递归类型，因为列表的每个子集本身都是一个列表。树是另一个例子，因为节点从树中移除，剩下的构造仍然是树。

形式上，递归类型 T 的值集将由表单上的递归集方程式定义：

T = …… T …

递归集方程可以有许多解，但是这样的方程总是具有最小解，其是每个其他解的子集。

作为一个实际例子，考虑这个 Haskell 定义的列表类型，

data List a = Nil | Cons a (List a)

意思是 a 的列表是空列表或包含’a’（列表的头部）和另一个列表（尾部）的 cons 单元。