Recursive definition

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 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". 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 an infinite regress. That recursive definitions are valid – meaning that a recursive definition identifies a unique function – is a theorem of set theory known as the recursion theorem, 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 (i.e., base case) is given, and that for , an algorithm is given for determining in terms of , f(0), f(1), \dots, f(n-1) (i.e., 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 James Munkres' Topology. However, a specific case (domain is restricted to the positive integers instead of any well-ordered set) of the general recursive definition will be given below. Principle of recursive definition Let be a set and let be an element of . If is a function which assigns to each function mapping a nonempty section of the positive integers into , an element of , then there exists a unique function h : \Z_+ \to A such that : \begin{align} h(1) &= a_0 \\ h(i) &= \rho \left(h|_{\{1,2,\ldots,i-1\}}\right) \text{ for } i>1. \end{align} ==Examples of recursive definitions==

Elementary functions Addition is defined recursively based on counting as :\begin{align} & 0 + a = a, \\ & (1+n) + a = 1 + (n+a). \end{align} Multiplication is defined recursively as :\begin{align} & 0 \cdot a = 0, \\ & (1+n) \cdot a = a + n \cdot a. \end{align} Exponentiation is defined recursively as :\begin{align} & a^0 = 1, \\ & a^{1+n} = a \cdot a^n. \end{align} Binomial coefficients can be defined recursively as :\begin{align} & \binom{a}{0} = 1, \\ & \binom{1+a}{1+n} = \frac{(1+a)\binom{a}{n}}{1+n}. \end{align} Prime numbers The set of prime numbers can be defined as the unique set of positive integers satisfying • 2 is 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 2 is the base case; checking the primality of any larger integer by this definition requires knowing the primality of every integer between 2 and , which is well defined by this definition. That last point can be proved by induction on , 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. Non-negative even numbers The even numbers can be defined as consisting of • 0 is in the set of non-negative evens (basis clause), • For any element in the set , is in (inductive clause), • Nothing is in unless it is obtained from the basis and inductive clauses (extremal clause). Well formed formula The notion of a well-formed formula (wff) in propositional logic is defined recursively as the smallest set satisfying the three rules: • is a wff if is a propositional variable. • is a wff if is a wff. • is a wff if and are wffs and • is one of the logical connectives ∨, ∧, →, or ↔. The definition can be used to determine whether any particular string of symbols is a wff: • is a wff, because the propositional variables and are wffs and is a logical connective. • is a wff, because is a wff. • is a wff, because and are wffs and is a logical connective. ==Recursive definitions as logic programs==

Logic programs can be understood as sets of recursive definitions. For example, the recursive definition of even number can be written as the logic program: even(0). even(s(s(X))) :- even(X). Here :- represents if, and s(X) represents the successor of X, namely X+1, as in Peano arithmetic. The logic programming language Prolog uses backward reasoning to solve goals and answer queries. For example, given the query ?- even(s(s(0))) it produces the answer true. Given the query ?- even(s(0)) it produces the answer false. 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 = 0 X = 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 by negation as failure, as in the definition: even(0). even(s(X)) :- not(even(X)). == See also ==