Recursion

The Sierpinski triangle—a confined recursion of triangles that form a fractal

Recursive Definition=

In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set. Some examples of recursively-definable objects include factorials, natural numbers, Fibonacci numbers, and the Cantor ternary set.

A recursive definition of a function 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 numbers 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 {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. 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.

Examples of recursive definitions

Elementary functions

Addition is defined recursively based on counting as

$0+a=a,$

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

Multiplication is defined recursively as

$0a=0,$

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

Exponentiation is defined recursively as

$a^{0}=1,$

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

Binomial coefficients can be defined recursively as

${\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 be 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 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.

Proofs with recursion

Example: the natural numbers

The canonical example of a recursively defined set is given by the natural numbers:

0 is in $\mathbb {N}$

if n is in $\mathbb {N}$, then n + 1 is in $\mathbb {N}$

The set of natural numbers is the smallest set satisfying the previous two properties.

In mathematical logic, the Peano axioms (or Peano postulates or Dedekind–Peano axioms), are axioms for the natural numbers presented in the 19th century by the German mathematician Richard Dedekind and by the Italian mathematician Giuseppe Peano. The Peano Axioms define the natural numbers referring to a recursive successor function and addition and multiplication as recursive functions.

Example: Proof procedure

Another interesting example is the set of all "provable" propositions in an axiomatic system that are defined in terms of a proof procedure which is inductively (or recursively) defined as follows:

• If a proposition is an axiom, it is a provable proposition.
• If a proposition can be derived from true reachable propositions by means of inference rules, it is a provable proposition.
• The set of provable propositions is the smallest set of propositions satisfying these conditions.

Finite subdivision rules

Finite subdivision rules are a geometric form of recursion, which can be used to create fractal-like images. A subdivision rule starts with a collection of polygons labelled by finitely many labels, and then each polygon is subdivided into smaller labelled polygons in a way that depends only on the labels of the original polygon. This process can be iterated. The standard `middle thirds' technique for creating the Cantor set is a subdivision rule, as is barycentric subdivision.

Functional recursion

A function may be recursively defined in terms of itself. A familiar example is the Fibonacci number sequence: F(n) = F(n − 1) + F(n − 2). For such a definition to be useful, it must be reducible to non-recursively defined values: in this case F(0) = 0 and F(1) = 1.

A famous recursive function is the Ackermann function, which, unlike the Fibonacci sequence, cannot be expressed without recursion.

Proofs involving recursive definitions

Applying the standard technique of proof by cases to recursively defined sets or functions, as in the preceding sections, yields structural induction — a powerful generalization of mathematical induction widely used to derive proofs in mathematical logic and computer science.

Recursive optimization

Dynamic programming is an approach to optimization that restates a multiperiod or multistep optimization problem in recursive form. The key result in dynamic programming is the Bellman equation, which writes the value of the optimization problem at an earlier time (or earlier step) in terms of its value at a later time (or later step).

The recursion theorem

In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set X, an element a of X and a function f: X → X, the theorem states that there is a unique function $F:\mathbb {N} \to X$ (where $\mathbb {N}$ denotes the set of natural numbers including zero) such that

$F(0)=a$

$F(n+1)=f(F(n))$

for any natural number n.

Proof of uniqueness

Take two functions $F:\mathbb {N} \to X$ and $G:\mathbb {N} \to X$ such that:

$F(0)=a$

$G(0)=a$

$F(n+1)=f(F(n))$

$G(n+1)=f(G(n))$

where a is an element of X.

It can be proved by mathematical induction that F(n) = G(n) for all natural numbers n:

Base Case: F(0) = a = G(0) so the equality holds for n = 0.

Inductive Step: Suppose F(k) = G(k) for some $k\in \mathbb {N}$. Then F(k + 1) = f(F(k)) = f(G(k)) = G(k + 1).

Hence F(k) = G(k) implies F(k + 1) = G(k + 1).

By induction, F(n) = G(n) for all $n\in \mathbb {N}$.

Resources

• Recursion, Wikipedia
• Recursive definition, Wikipedia