recursive definition



mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includ ...
, 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
factorials In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
Fibonacci numbers In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
, and the Cantor ternary set. A recursive definition of a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orient ...
defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, the factorial function ''n''! is defined by the rules :0! = 1. :(''n'' + 1)! = (''n'' + 1)·''n''!. This definition is valid for each natural number ''n'', because the recursion eventually reaches the base case of 0. The definition may also be thought of as giving a procedure for computing the value of the function ''n''!, starting from ''n'' = 0 and proceeding onwards with ''n'' = 1, ''n'' = 2, ''n'' = 3 etc. The recursion theorem states that such a definition indeed defines a function that is unique. The proof uses mathematical induction. An inductive definition of a set describes the elements in a set in terms of other elements in the set. For example, one definition of the set N of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s is: #1 is in N. #If an element ''n'' is in N then ''n'' + 1 is in N. #N is the intersection of all sets satisfying (1) and (2). There are many sets that satisfy (1) and (2) – for example, the set satisfies the definition. However, condition (3) specifies the set of natural numbers by removing the sets with extraneous members. Note that this definition assumes that N is contained in a larger set (such as the set of real numbers) — in which the operation + is defined. Properties of recursively defined functions and sets can often be proved by an induction principle that follows the recursive definition. For example, the definition of the natural numbers presented here directly implies the principle of mathematical induction for natural numbers: if a property holds of the natural number 0 (or 1), and the property holds of ''n''+1 whenever it holds of ''n'', then the property holds of all natural numbers (Aczel 1977:742).

Form of recursive definitions

Most recursive definitions have two foundations: a base case (basis) and an inductive clause. The difference between a
circular definition A circular definition is a description that uses the term(s) being defined as part of the description or assumes that the term(s) being described are already known. There are several kinds of circular definition, and several ways of characteri ...
and a recursive definition is that a recursive definition must always have ''base cases'', cases that satisfy the definition ''without'' being defined in terms of the definition itself, and that all other instances in the inductive clauses must be "smaller" in some sense (i.e., ''closer'' to those base cases that terminate the recursion) — a rule also known as "recur only with a simpler case". In contrast, a circular definition may have no base case, and even may define the value of a function in terms of that value itself — rather than on other values of the function. Such a situation would lead to an
infinite regress An infinite regress is an infinite series of entities governed by a recursive principle that determines how each entity in the series depends on or is produced by its predecessor. In the epistemic regress, for example, a belief is justified be ...
. That recursive definitions are valid – meaning that a recursive definition identifies a unique function – is a theorem of set theory known as the recursion theorem, the proof of which is non-trivial.For a proof of Recursion Theorem, se
''On Mathematical Induction'' (1960) by Leon Henkin
Where the domain of the function is the natural numbers, sufficient conditions for the definition to be valid are that the value of (i.e., base case) is given, and that for , an algorithm is given for determining in terms of (i.e., inductive clause). More generally, recursive definitions of functions can be made whenever the domain is a well-ordered set, using the principle of
transfinite recursion Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for a ...
. The formal criteria for what constitutes a valid recursive definition are more complex for the general case. An outline of the general proof and the criteria can be found in James Munkres' ''Topology''. However, a specific case (domain is restricted to the positive
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s instead of any well-ordered set) of the general recursive definition will be given below.

Principle of recursive definition

Let be a set and let be an element of . If is a function which assigns to each function mapping a nonempty section of the positive integers into , an element of , then there exists a unique function h : \Z_+ \to A such that : h(1)=a_0 : h(i)=\rho(h, _) \text i>1.

Examples of recursive definitions

Elementary functions

Addition Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' of ...
is defined recursively based on counting as :0 + a = a, :(1+n) + a = 1 + (n+a).
Multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being addi ...
is defined recursively as :0 a = 0, :(1+n)a = a + na.
Exponentiation Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to r ...
is defined recursively as :a^0 = 1, :a^ = a a^n. Binomial coefficients can be defined recursively as :\binom = 1, :\binom = \frac.

Prime numbers

The set of
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s can be defined as the unique set of positive integers satisfying * 1 is not a prime number, * any other positive integer is a prime number if and only if it is not divisible by any prime number smaller than itself. The primality of the integer 1 is the base case; checking the primality of any larger integer ''X'' by this definition requires knowing the primality of every integer between 1 and ''X'', which is well defined by this definition. That last point can be proved by induction on ''X'', for which it is essential that the second clause says "if and only if"; if it had just said "if", the primality of, for instance, the number 4 would not be clear, and the further application of the second clause would be impossible.

Non-negative even numbers

The even numbers can be defined as consisting of * 0 is in the set ''E'' of non-negative evens (basis clause), * For any element ''x'' in the set ''E'', ''x'' + 2 is in ''E'' (inductive clause), * Nothing is in ''E'' unless it is obtained from the basis and inductive clauses (extremal clause).

Well formed formulas

It is chiefly in logic or computer programming that recursive definitions are found. For example, a
well-formed formula In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language. A formal language can ...
(wff) can be defined as: #a symbol which stands for a proposition – like p means "Connor is a lawyer." #The negation symbol, followed by a wff – like Np means "It is not true that Connor is a lawyer." #Any of the four binary connectives (''C'', ''A'', ''K'', or ''E'') followed by two wffs. The symbol K means "both are true", so Kpq may mean "Connor is a lawyer, and Mary likes music." The value of such a recursive definition is that it can be used to determine whether any particular string of symbols is "well formed". * Kpq is well formed, because it is K followed by the atomic wffs p and q. * NKpq is well formed, because it is N followed by Kpq, which is in turn a wff. * KNpNq is K followed by Np and Nq; and Np is a wff, etc.

See also

* Mathematical induction *
Recursive data type 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 usuall ...
s *
Recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
* Structural induction



* * * {{DEFAULTSORT:Recursive Definition Definition Mathematical logic Theoretical computer science Recursion