In mathematical logic

Mathematical logic

Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

 and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, 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

Factorial

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

 function n! is defined by the rules

0! = 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

Well-founded relation

In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...

. 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..

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

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s is:

1. 1 is in N.
2. If an element n is in N then n+1 is in N.
3. N is the smallest set 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

Mathematical induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

 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 definition have three foundations: a base case (basis), an inductive clause, and an extremal clause.

The difference between a circular definition

Circular definition

A circular definition is one that uses the term being defined as a part of the definition or assumes a prior understanding of the term being defined. Either the audience must already know the meaning of the key term, or the definition is deficient in including the term to be defined in the...

 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

Infinite regress

An infinite regress in a series of propositions arises if the truth of proposition P1 requires the support of proposition P2, the truth of proposition P2 requires the support of proposition P3, .....

.

Prime numbers

The set of prime number

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

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 evenly 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
   Proposition
   In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...
   
    - 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 connective
   Connective
   Connective may be referring to:* Bains::connective* Logical connective* Connective tissue* Discourse connective, in linguistics, a word or phrase like "therefore" or "in other words"....
   
   s (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.