Recursion

This is an old revision of this page, as edited by Jonhays0 (talk | contribs) at 17:21, 28 September 2003. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Revision as of 17:21, 28 September 2003 by Jonhays0 (talk | contribs)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Recursion is a way of specifying a process by means of itself. More precisely (and to dispel the appearance of circularity in the definition), "complicated" instances of the process are defined in terms of "simpler" instances, and the "simplest" instances are given explicitly.

Mathematical linguist, Noam Chomsky, produced evidence that unlimited extension of a language such as English is possible only by the recursive device of embedding sentences in sentences. Thus, a talky little girl may say, "Dorothy, who met the wicked Witch of the West in Munchkin Land where her wicked Witch sister was killed, liquidated her with a pail of water." Clearly, two simple sentences -- "Dorothy met the Wicked Witch of the West in Munchkin Land", and "Her sister was killed in Munchkin Land" -- can be embedded in a third sentence, "Dorothy liquidated her with a pail of water", to obtain a very talky sentence.

Here is another, perhaps simpler way to understand recursive processes:

Are we done yet? If so, return the results. Without such a termination condition a recursion would go on forever.
If not, simplify the problem, solve those simpler problem(s), and assemble the results into a solution for the original problem. Then return that solution.

Examples of mathematical objects often defined recursively are functions and sets.

Recursively Defined Sets

Example: the natural numbers

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

0 is in N

if n is in N, then n+1 is in N

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

Here's an alternative recursive definition of N:

0, 1 are in N;

if n and n+1 are in N, then n+2 is in N;

N is the smallest set satisfying the previous two properties.

Example: true propositions

Another interesting example is the set of all true propositions in an axiomatic system.

if a proposition is an axiom, it is a true proposition.

if a proposition can be obtained from true propositions by means of inference rules, it is a true proposition.

The set of true propositions is the smallest set of propositions satisfying these conditions.

This set is called 'true propositions' for lack of a better name: in nonconstructive approaches to the foundations of mathematics, the set of true propositions is larger than the set recursively constructed from the axioms and rules of inference.

(It needs to be pointed out that determining whether a certain object is in a recursively defined set is not an algorithmic task.)

Formal definition

(Insert definition of recursively defined set here)

Recursively Defined Functions

Functions whose domains can be recursively defined can be given recursive definitions patterned after the recursive definition of their domain.

The canonical example of a recursively defined function is the following definition of the factorial function f(n):

f(0) = 1

f(n) = n · f(n-1) for any natural number n > 0

Given this definition, also called a recurrence relation, we work out f(3) as follows:

f(3) = 3 · f(3-1)
     = 3 · f(2)
     = 3 · 2 · f(2-1)
     = 3 · 2 · f(1) 
     = 3 · 2 · 1 · f(1-1)
     = 3 · 2 · 1 · f(0)
     = 3 · 2 · 1 · 1
     = 6

Another example is the definition of Fibonacci numbers.

Recursive algorithms

A common method of simplification is to divide a problem into subproblems of the same type. As a programming technique is called divide and conquer and is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming.

Virtually all programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer keeps track of the various instances of the function by using a stack. Conversely, every recursive function can be transformed into an iterative function by using a stack.

Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without use of iteration, and conversely.

Indeed, some languages designed for logic programming and functional programming provide recursion as the only means of repetition directly available to the programmer. Such languages generally make tail recursion as efficient as iteration, letting programmers express other repetition structures (such as Scheme's map and for) in terms of recursion.

Recursion is deeply embedded in the theory of computation, with the theoretical equivalence of recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer.

John McCarthy's function, McCarthy's 91 is another example of a recursive function.

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 : N -> X (where N denotes the set of natural numbers) such that

F(0) = a

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

for any natural number n.

Proof of Uniqueness

Take two functions f and g of domain N and codomain A 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 A. We want to prove that f = g. Two functions are equal if they:

i. have equal domains/codomains;

ii. have the same graphic.

i. Done!

ii. Mathematical induction: for all n in N, f(n) = g(n)? (We shall call this condition, say, Eq(n)):

1.:Eq(0) iff f(0) = g(0) iff a = a. Done!

2.:Let n be an element of N. Assuming that Eq(n) holds, we want to show that Eq(n+1) holds as well, which is easy because: f(n+1) = F(f(n)) = F(g(n)) = g(n+1). Done!

Proof of Existence

We define F on zero, then one and so on. Define F(0) = a; Now assuming that F has been defined on all numbers less than equal to n we define F(N+1) = f( F(N) ). Note that since F(N) has been defined by hypothesis and that f is a function X to X so the right hand side is indeed a member of X and so this a correct definition. Alternatively, and informally, F(N) is the result of applying f to a N times.

List of recurrence relations or algorithms

Recurrence relations are equations which define themselves recursively. Some specific kinds of recurrence relation can be "solved" to obtain a nonrecursive definition.

Some common recurrence relations are:

Factorial -- n! = n * (n - 1) * ... * 1
Fibonacci numbers -- f(n) = f(n - 1) + f(n - 2)
Catalan numbers -- C(2n, n)/(n + 1)
Computing compound interests
The tower of Hanoi
Ackermann's function
Population growth

Misplaced Pages