Recursive definition

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

A recursive definition (or inductive definition) in mathematical logic and computer science is used to define the elements in a set in terms of other elements in the set (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 for all n, because the recursion eventually reaches the base case of 0. The definition may also be thought of as giving a procedure describing how to construct 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. 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 numbers is:

1. 1 is in N.
2. If an element n is in N then n+1 is in N.
3. N is the intersection of all sets satisfying (1) and (2).

There are many sets that satisfy (1) and (2) - for example, the set {1, 1.649, 2, 2.649, 3, 3.649, ...} satisfies the definition. However, condition (3) specifies the set of natural numbers by removing the sets with extraneous members.

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, 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 definitions have two foundations: a base case (basis) and an inductive 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.

That recursive definitions are valid - meaning that a recursive definition identifies a unique function - is a theorem of set theory, the proof of which is non-trivial. Where the domain of the function is the natural numbers, sufficient conditions for the definition to be valid are that the value of $f(0)$ is given (base case) and that, for n>0, an algorithm is given for determining for determining $f(n)$ in terms of $n, f(0), f(1), ...,f(n-1)$ (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. 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 Munkres.

Examples of recursive definitions

Elementary functions

Addition is defined recursively based on counting

$0+a=a$

$(1+n)+a=1+(n+a)$

Multiplication is defined recursively

$0 a=0$

$(1+n)a=a+na$

Exponentiation is defined recursively

$a^0=1$

$a^{1+n}=a a^n$

Binomial coefficients are defined recursively

$\binom{a}{0}=1$

$\binom{1+a}{1+n}=\frac{(1+a)\binom{a}{n}}{1+n}$

Prime numbers

The set of prime numbers 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 proved by induction on X, for which it is essential that the second clause says "if and only if"; if it had said just "if" the primality of for instance 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 (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.

See also

• Recursive data types
• Recursion
• Mathematical induction

References

• Paul Halmos: Naive set theory, van Nostrand, 1960
• 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-7637-7206-2.