在计算机程式语言，一个递归类型（也被称为递归定义，电感定义或感应数据类型）是一种数据类型，选择那些包含相同类型的其它值的值。递归类型的数据通常被视为有向图。
递归在计算机科学中的一个重要套用是定义动态数据结构，如列表和树。递归数据结构可以回响运行时要求动态增长到任意大的大小; 相反，必须在编译时设定静态数组的大小要求。
有时，术语“归纳数据类型”用于不一定递归的代数数据类型。
基本介绍
- 中文名：递归类型
- 外文名：Recursive data type
- 学科：计算机科学
简介
在计算机程式语言中，递归类型（又名：递归定义、隐含类型或隐含定义）是一种特殊的数据类型，它表示自身内部可能包含其它的同样类型的值。
範例
以下是一个在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[1], ..., t[k]]t: v f
森林f由树木列表组成，而树木t由一对值v和森林f（其子）组成。这个定义是优雅的，并且易于抽象地工作（例如当证明有关树的属性的定理时），因为它用简单的术语表示树：一种类型的列表和一种两种类型的对。
通过内联林的定义，可以将此相互递归定义转换为单个递归定义：
t：v [t [1]，...，t [k]]
树t由一对值v和树列表（它的孩子）组成。这个定义更紧凑，但有点混乱：一棵树由一对类型和另一种类型组成，需要解开才能证明结果。
在标準ML中，树和林数据类型可以相互递归地定义如下，允许空树：
datatype 'a tree = Empty | Node of 'a * 'a forestand 'a forest = Nil | Cons of 'a tree * 'a forest