Recursive definition

Four stages in the construction of a Koch snowflake. As with many other fractals, the stages are obtained via a recursive definition.

In mathematical logic and computer science, a recursive definition (or inductive definition) is used to define an object in terms of itself (Aczel 1978:740ff).

A recursive definition of a function defines values of the functions for some inputs in terms of the values of the same function for other inputs. For example, the factorial function n! is defined by the rules

0! = 1.

(n+1)! = (n+1)· n!.

This definition is valid because, for all n, the recursion eventually reaches the base case of 0. Thus the definition is well-founded.

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 numbers is:

1. 0 is in N.
2. If an element n is in N then n+1 is in N.
3. N is the smallest set such satisfying (1) and (2).

There are many sets that satisfy (1) and (2); clause (3) makes the definition precise by choosing the smallest such set as N.

Properties of recursively defined functions and sets can often be proved by an induction principle the 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, and the property holds of n+1 whenever it holds of n, then the property holds of all natural numbers (Aczel 1978:742).

Form of recursive definitions

Most recursive definition have three foundations: a base case (basis), an inductive clause, and an extremal clause.

The difference between a circular definition 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 all other cases comprising the definition must be "smaller" (closer to those base cases that terminate the recursion) in some sense. In contrast, a circular definition may have no base case, and 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.

Examples of recursive definitions

Prime numbers

The prime numbers can be defined as consisting of:

• 2, the smallest prime;
• each positive integer which is not evenly divisible by any of the primes smaller than itself.

The integer 2 is our base case; checking the primality of any larger integer X requires us to know the primality of every integer between X and 2, but each such integer is closer to our base case of 2 than X is.

Non-negative even numbers

The even numbers can be defined as consisting of

• 0 is in the set N of non-negative evens (basis clause)
• For any element x in the set N, x+2 is in N (inductive clause)
• Nothing is in N 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 (wff) can be defined as:

1. a symbol which stands for a proposition - like p means "Connor is a lawyer."
2. The negation symbol, followed by a wff - like Np means "It is not true that Connor is a lawyer."
3. 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's K followed by the atomic wffs p and q.
• NKpq is well formed, because it's N followed by Kpq, which is in turn a wff.
• KNpNq is K followed by Np and Nq; and Np is a wff, etc.

Recursive definitions in common parlance and philosophical terminology

In common parlance and philosophical terminology, definitions often contain recursive elements.

• "Nothing" is defined by properties it does not have. "There's nothing in that room." describes that there is nothing notable in the room, most probably there is air in the room, but the air would be irrelevant as it does not correspond to the necessary properties that would have been defined or implied in the preceding sentence. The phrases "the nothing(ness)" and "absolute nothing(ness)" would describe something that lacks any property, something to which nothing can be described to, indeed something that does not exist, not in this universe, not in one's imagination, nowhere.
• "Science" may be seen as the practice of describing the empirical or observable facts of nature (or at least trying to do so). As scientists only consider nature for as far as it can be observed, they tend to see non-observable things as supernatural and/or not existing in this universe. Supernatural or paranormal phenomena, if they exist, would only be described as thus because they go beyond how nature is commonly perceived.

See also

• Recursive data types

References

• P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.), ISBN 0-444-86388-5
• James L. Hein (2009), Discrete Structures, Logic, and Computability. ISBN 0-763-77206-2