In computer
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s, a recursive data type (also known as a recursively defined, inductively defined or inductive data type) is a
data type
In computer science and computer programming, a data type (or simply type) is a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these ...
for values that may contain other values of the same type. Data of recursive types are usually viewed as
directed graphs.
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 for
algebraic data type
In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite data type, i.e., a data type formed by combining other types.
Two common classes of algebraic types are product ty ...
s which are not necessarily recursive.
Example
An example is the
list
A list is a Set (mathematics), set of discrete items of information collected and set forth in some format for utility, entertainment, or other purposes. A list may be memorialized in any number of ways, including existing only in the mind of t ...
type, in
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
:
data List a = Nil , Cons a (List a)
This indicates that a list of a's is either an empty list or a cons cell containing an 'a' (the "head" of the list) and another list (the "tail").
Another example is a similar singly linked type in
Java
Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...
:
class List
This indicates that non-empty list of type ''E'' contains a data member of type ''E'', and a reference to another List object for the rest of the list (or a
null reference to indicate that this is the end of the list).
Mutually recursive data types
Data types can also be defined by
mutual recursion. The most important basic example of this is a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
, which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:
f:
[1 ..., t[k">[1.html" ;"title="[1">[1 ..., t[k
t: v f
A forest ''f'' consists of a list of trees, while a tree ''t'' consists of a pair of a value ''v'' and a forest ''f'' (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
[1 ..., t[k">[1.html" ;"title="[1">[1 ..., t[k
A tree ''t'' consists of a pair of a value ''v'' 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.
In Standard ML, the tree and forest data types can be mutually recursively defined as follows, allowing empty trees:
datatype 'a tree = Empty , Node of 'a * 'a forest
and 'a forest = Nil , Cons of 'a tree * 'a forest
In Haskell, the tree and forest data types can be defined similarly:
data Tree a = Empty
, Node (a, Forest a)
data Forest a = Nil
, Cons (Tree a) (Forest a)
Theory
In
type theory
In mathematics and theoretical computer science, a type theory is the formal presentation of a specific type system. Type theory is the academic study of type systems.
Some type theories serve as alternatives to set theory as a foundation of ...
, a recursive type has the general form ''μα''.''T'' where the
type variable
In type theory and programming languages, a type variable is a mathematical variable ranging over types. Even in programming languages that allow mutable variables, a type variable remains an abstraction, in the sense that it does not correspond ...
''α'' may appear in the type ''T'' and stands for the entire type itself.
For example, the natural numbers (see
Peano arithmetic) may be defined by the Haskell datatype:
data Nat = Zero , Succ Nat
In type theory, we would say:
where the two arms of the
sum type represent the Zero and Succ data constructors. Zero takes no arguments (thus represented by the
unit type
In the area of mathematical logic and computer science known as type theory, a unit type is a type that allows only one value (and thus can hold no information). The carrier (underlying set) associated with a unit type can be any singleton set. ...
) and Succ takes another Nat (thus another element of
).
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.
Isorecursive types
With isorecursive types, the recursive type
and its expansion (or ''unrolling'')
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
between them. To be precise:
roll : T mu\alpha.T/\alpha\to \mu\alpha.T and
unroll : \mu\alpha.T \to T mu\alpha.T/\alpha/math>, and these two are inverse function
In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ .
For a function f\colon ...
s.
Equirecursive types
Under equirecursive rules, a recursive type
\mu \alpha . T and its unrolling
T mu\alpha.T/\alpha/math> are ''equal'' – 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 and type inference
Type inference, sometimes called type reconstruction, refers to the automatic detection of the type of an expression in a formal language. These include programming languages and mathematical type systems, but also natural languages in some bran ...
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.
[
]
Isorecursive types capture the form of self-referential (or mutually referential) type definitions seen in nominal
object-oriented
Object-oriented programming (OOP) is a programming paradigm based on the concept of '' objects''. Objects can contain data (called fields, attributes or properties) and have actions they can perform (called procedures or methods and impleme ...
programming languages, and also arise in type-theoretic semantics of objects and
class
Class, Classes, or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used d ...
es. In functional programming languages, isorecursive types (in the guise of datatypes) are common too.
Recursive type synonyms
In
TypeScript
TypeScript (abbreviated as TS) is a high-level programming language that adds static typing with optional type annotations to JavaScript. It is designed for developing large applications and transpiles to JavaScript. It is developed by Micr ...
, recursion is allowed in type aliases.
(More) Recursive Type Aliases - Announcing TypeScript 3.7 - TypeScript
/ref> Thus, the following example is allowed.
type Tree = number , Tree[];
let tree: Tree = [1, [2, 3;
However, recursion is not allowed in type synonyms in Miranda programming language, Miranda, OCaml (unless -rectypes
flag is used or it is a record or variant), or Haskell; so, for example the following Haskell types are illegal:
type Bad = (Int, Bad)
type Evil = Bool -> Evil
Instead, they must be wrapped inside an algebraic data type (even if they only has one constructor):
data Good = Pair Int Good
data Fine = Fun (Bool -> Fine)
This is because type synonyms, like typedef
typedef is a reserved keyword in the programming languages C, C++, and Objective-C. It is used to create an additional name (''alias'') for another data type, but does not create a new type, except in the obscure case of a qualified typedef of ...
s in C, are replaced with their definition at compile time. (Type synonyms are not "real" types; they are just "aliases" for convenience of the programmer.) But if this is attempted with a recursive type, it will loop infinitely because no matter how many times the alias is substituted, it still refers to itself, e.g. "Bad" will grow indefinitely: Bad
→ (Int, Bad)
→ (Int, (Int, Bad))
→ ...
.
Another way to see it is that a level of indirection (the algebraic data type) is required to allow the isorecursive type system to figure out when to ''roll'' and ''unroll''.
See also
* Recursive definition
In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set ( Aczel 1977:740ff). Some examples of recursively definable objects include fact ...
* Algebraic data type
In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite data type, i.e., a data type formed by combining other types.
Two common classes of algebraic types are product ty ...
* Inductive type
In type theory, a system has inductive types if it has facilities for creating a new type from constants and functions that create terms of that type. The feature serves a role similar to data structures in a programming language and allows a ty ...
* Node (computer science)
A node is a basic unit of a data structure, such as a linked list or Tree (data structure), tree data structure. Nodes contain data and also may link to other nodes. Links between nodes are often implemented by Pointer (computer programming), point ...
References
Sources
*
{{Data types
Data types
Type theory