Inmathematics andcomputer science, arecursive definition, orinductive definition, is used to define theelements in aset in terms of other elements in the set (Aczel 1977:740ff). Some examples of recursively definable objects includefactorials,natural numbers,Fibonacci numbers, and theCantor ternary set.
Arecursivedefinition of afunction defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, thefactorial functionn! is defined by the rules
This definition is valid for each natural numbern, because the recursion eventually reaches thebase case of 0. The definition may also be thought of as giving a procedure for computing the value of the function n!, starting fromn = 0 and proceeding onwards withn = 1, 2, 3 etc.
The recursion theorem states that such a definition indeed defines a function that is unique. The proof usesmathematical induction.[1]
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 ofnatural numbers is:
There are many sets that satisfy (1) and (2) – for example, the set{0, 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 (or 1), and the property holds ofn + 1 whenever it holds ofn, then the property holds of all natural numbers (Aczel 1977:742).
Most recursive definitions have two foundations: a base case (basis) and an inductive clause.
The difference between acircular definition and a recursive definition is that a recursive definition must always havebase cases, cases that satisfy the definitionwithout 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".[2]
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 aninfinite regress.
That recursive definitions are valid – meaning that a recursive definition identifies a unique function – is a theorem of set theory known as therecursion theorem, the proof of which is non-trivial.[3] Where the domain of the function is the natural numbers, sufficient conditions for the definition to be valid are that the value off(0) (i.e., base case) is given, and that forn > 0, an algorithm is given for determiningf(n) in terms ofn, (i.e., inductive clause).
More generally, recursive definitions of functions can be made whenever the domain is awell-ordered set, using the principle oftransfinite 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 inJames Munkres'Topology. However, a specific case (domain is restricted to the positiveintegers instead of any well-ordered set) of the general recursive definition will be given below.[4]
LetA be a set and leta0 be an element ofA. Ifρ is a function which assigns to each functionf mapping a nonempty section of the positive integers intoA, an element ofA, then there exists a unique function such that
Addition is defined recursively based on counting as
Multiplication is defined recursively as
Exponentiation is defined recursively as
Binomial coefficients can be defined recursively as
The set ofprime numbers can be defined as the unique set of positive integers satisfying
The primality of the integer 2 is the base case; checking the primality of any larger integerX by this definition requires knowing the primality of every integer between 2 andX, which is well defined by this definition. That last point can be proved by induction onX, 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.
Theeven numbers can be defined as consisting of
The notion of awell-formed formula (wff) in propositional logic is defined recursively as the smallest set satisfying the three rules:
The definition can be used to determine whether any particular string of symbols is a wff:
Logic programs can be understood as sets of recursivedefinitions.[5][6] For example, the recursive definition of even number can be written as the logic program:
even(0).even(s(s(X))):-even(X).
Here:- representsif, ands(X) represents the successor ofX, namelyX+1, as inPeano arithmetic.
The logic programming languageProlog usesbackward reasoning to solve goals and answer queries. For example, given the query?-even(s(s(0))) it produces the answertrue. Given the query?-even(s(0)) it produces the answerfalse.
The program can be used not only to check whether a query is true, but also to generate answers that are true. For example:
?-even(X).X=0X=s(s(0))X=s(s(s(s(0))))X=s(s(s(s(s(s(0)))))).....
Logic programs significantly extend recursive definitions by including the use of negative conditions, implemented bynegation as failure, as in the definition:
even(0).even(s(X)):-not(even(X)).