Incomputer programming, arecursive data type is adata type whose definition contains values of the same type. It is also known as arecursively defined,inductively defined orinductive data type. Data of recursive types are usually viewed asdirected graphs.^{[citation needed]}

An important application of recursion in computer science is in defining dynamic data structures such as Lists and Trees. Recursive data structures can dynamically grow to an arbitrarily large size in response to runtime requirements; in contrast, a static array's size requirements must be set at compile time.

Sometimes the term "inductive data type" is used foralgebraic data types which are not necessarily recursive.

An example is thelist type, inHaskell:

dataLista=Nil|Consa(Lista)

This indicates that a list of a's is either an empty list or acons cell containing an 'a' (the "head" of the list) and another list (the "tail").

Another example is a similar singly linked type inJava:

publicclassLinkedList<E>{privateEvalue;privateLinkedList<E>next;// constructor and methods...}

This indicates that non-empty list of typeE contains a data member of typeE, and a reference to another List object for the rest of the list (or anull reference to indicate that this is the end of the list).

Data types can also be defined bymutual recursion. The most important basic example of this is atree, which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:

f: [t[1], ..., t[k]]t: v f

A forestf consists of a list of trees, while a treet consists of a pair of a valuev and a forestf (its children). This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types.

This mutually recursive definition can be converted to a singly recursive definition by inlining the definition of a forest:

t: v [t[1], ..., t[k]]

A treet consists of a pair of a valuev and a list of trees (its children). This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list another, which require disentangling to prove results about.

InStandard ML, the tree and forest data types can be mutually recursively defined as follows, allowing empty trees:^[1]

datatype'atree=Empty|Nodeof'a*'aforestand'aforest=Nil|Consof'atree*'aforest

In Haskell, the tree and forest data types can be defined similarly:

dataTreea=Empty|Node(a,Foresta)dataForesta=Nil|Cons(Treea)(Foresta)

Intype theory, a recursive type has the general formμα.T where thetype variableα may appear in the typeT and stands for the entire type itself.

For example, the natural numbers (seePeano arithmetic) may be defined by the Haskell datatype:

dataNat=Zero|SuccNat

In type theory, we would say:${\displaystyle \text{nat}=\mu \alpha .1+\alpha }$ where the two arms of thesum type represent the Zero and Succ data constructors. Zero takes no arguments (thus represented by theunit type) and Succ takes another Nat (thus another element of${\displaystyle \mu \alpha .1+\alpha }$).

There are two forms of recursive types: the so-called isorecursive types, and equirecursive types. The two forms differ in how terms of a recursive type are introduced and eliminated.

With isorecursive types, the recursive type${\displaystyle \mu \alpha .T}$ and its expansion (orunrolling)${\displaystyle T[\mu \alpha .T/\alpha ]}$ (where the notation${\displaystyle X[Y/Z]}$ indicates that all instances of Z are replaced with Y in X) are distinct (and disjoint) types with special term constructs, usually calledroll andunroll, that form anisomorphism between them. To be precise:${\displaystyle roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T}$ and${\displaystyle unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]}$, and these two areinverse functions.

Under equirecursive rules, a recursive type${\displaystyle \mu \alpha .T}$ and its unrolling${\displaystyle T[\mu \alpha .T/\alpha ]}$ areequal – that is, those two type expressions are understood to denote the same type. In fact, most theories of equirecursive types go further and essentially specify that any two type expressions with the same "infinite expansion" are equivalent. As a result of these rules, equirecursive types contribute significantly more complexity to a type system than isorecursive types do. Algorithmic problems such as type checking andtype inference are more difficult for equirecursive types as well. Since direct comparison does not make sense on an equirecursive type, they can be converted into a canonical form in O(n log n) time, which can easily be compared.^[2]

Isorecursive types capture the form of self-referential (or mutually referential) type definitions seen in nominalobject-oriented programming languages, and also arise in type-theoretic semantics of objects andclasses. In functional programming languages, isorecursive types (in the guise of datatypes) are common too.^[3]

This sectionneeds expansion. You can help byadding to it.(August 2025)

InTypeScript, recursion is allowed in type aliases.^[4]

• Recursive definition
• Algebraic data type
• Inductive type
• Node (computer science)

• Harper, Robert (1998),Datatype Declarations, archived fromthe original on 1999-10-01

• Data types
• Type theory

• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from July 2022
• Articles to be expanded from August 2025
• All articles to be expanded