|
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.
An example of a recursive image
Recursion in language
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.
Niels K. Jerne, the 1984 Nobel Prize laureate in Medicine and
Physiology, used Chomsky's transformational-generative grammar model to explain the human immune system, equating
"components of a generative grammar ... with various features of protein structures." The title of Jerne's Stockholm
Nobel lecture was The Generative Grammar of the Immune System.
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.
A more humorous illustration goes: "In order to understand recursion, one must first understand recursion." Or
perhaps more accurate is the following due to Andrew Plotkin: "If you already know what recursion is, just remember the
answer. Otherwise, find someone who is standing closer to Douglas
Hofstadter than you are; then ask him or her what recursion is."
Examples of mathematical objects often defined recursively are functions, sets, and especially fractals.
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: The set of true reachable propositions
Another interesting example is the set of all true "reachable" propositions in an axiomatic system.
- if a proposition is an axiom, it is a true reachable proposition.
- if a proposition can be obtained from true reachable propositions by means of inference rules, it is a true reachable
proposition.
- The set of true reachable propositions is the smallest set of reachable propositions satisfying these conditions.
This set is called 'true reachable propositions' because: 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. See also Godels Incompleteness Theorem.
(Note 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
Recursive algorithms
A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this 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 (for most lanaguages
on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many
architectures, by using a stack, although other methods may
be used). 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.
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
[See Hungerford, "Algebra", first chapter on set theory]
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.
Recursive Definition of Recursion
- see Recursion (for further exemplification, if sought)
This is a common definition found in many geek dictionaries, including the jargon file.
Some common recurrence relations are:
See also
Further readings and references
- Richard Johnsonbaugh, Discrete Mathematics 5th edition. 1990 Macmillan
- Douglas Hofstadter, Gödel, Escher, Bach: an
Eternal Golden Braid (20th anniversary edition HarperCollins 1999) ISBN 0465026567
|