Рекурсивті дерек типінің анықтамасы

Data type that refers to itself in its definition

In computer programming languages, a recursive data type (also known as a recursively defined, inductively defined or inductive data type) is a data type 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 types which are not necessarily recursive.

With isorecursive types, the recursive type and its expansion (or unrolling) (where the notation indicates that all instances of Z are replaced with Y in X) are distinct (and disjoint) types with special term constructs, usually called roll and unroll, that form an isomorphism between them. To be precise: and , and these two are inverse functions.

Under equirecursive rules, a recursive type and its unrolling 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 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 programming languages, and also arise in type theoretic semantics of objects and classes. In functional programming languages, isorecursive types (in the guise of datatypes) are common too.