Recursive definition

From Encyclopedia of Mathematics
Jump to: navigation, search

A frequently used means (in mathematics) of defining a function, according to which the value of the function sought at a given point is defined by way of its values at preceding points (given a suitable relation of precedence). Recursive definitions of number-theoretic functions are the subjects of study in the theory of algorithms (see Recursion). In set theory they are constantly used to define functions on ordinals by transfinite recursion. On a wider scale, recursive definitions are studied in the theory of admissible sets, at the basis of which lies a certain synthesis of ideas in the theory of sets and algorithms (see [2]).


[1] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
[2] J. Barwise, "Admissible sets and structures" , Springer (1975)
How to Cite This Entry:
Recursive definition. N.V. Belyakin (originator), Encyclopedia of Mathematics. URL:
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098