什么是递归类型介绍
在计算机编程语言，一个递归类型（也被称为递归定义，电感定义或感应数据类型）是一种数据类型，选择那些包含相同类型的其它值的值。递归类型的数据通常被视为有向图。
递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以响应运行时要求动态增长到任意大的大小; 相反，必须在编译时设置静态数组的大小要求。
有时，术语“归纳数据类型”用于不一定递归的代数数据类型。
递归类型定义
在计算机编程语言中，递归类型（又名：递归定义、隐含类型或隐含定义）是一种特殊的数据类型，它表示自身内部可能包含其它的同样类型的值。
递归类型使用范例
以下是一个在Haskell中使用链表类型的一个列子：
data List a = Nil | Cons a (List a)
这表示a的链表s可以是一个空表或一个cons单元包含了一个\'a\'（链表的“头”）和另一个链表（“尾”）。
递归不允许在Miranda语言中和Haskell的同义类型中出现，所以以下的Haskell类型是非法的：
type Bad = (Int, Bad) type Evil = Bool -> Evil
相反地，表面上是相等的代数数据类型却是可以的：
data Good = Pair Int Good data Fine = Fun (Bool->Fine)
相互递归数据类型
数据类型也可以通过相互递归来定义。最重要的基本示例是树，可以根据森林（树木列表）相互递归地定义树。象征：
f: , ..., t]t: v f
森林f由树木列表组成，而树木t由一对值v和森林f（其子）组成。这个定义是优雅的，并且易于抽象地工作（例如当证明有关树的属性的定理时），因为它用简单的术语表示树：一种类型的列表和一种两种类型的对。
通过内联林的定义，可以将此相互递归定义转换为单个递归定义：
t：v ，...，t ]
树t由一对值v和树列表（它的孩子）组成。这个定义更紧凑，但有点混乱：一棵树由一对类型和另一种类型组成，需要解开才能证明结果。
在标准ML中，树和林数据类型可以相互递归地定义如下，允许空树：
datatype \'a tree = Empty | Node of \'a * \'a forestand \'a forest = Nil | Cons of \'a tree * \'a forest