Recursion: Difference between revisions

Revision as of 11:35, 24 May 2002

Revision as of 14:21, 24 May 2002

Line 1:

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

Examples of mathematical objects often defined recursively are functions[[function]]s and sets[[set]]s.

The canonical example of a recursively defined function is

Line 23:

'''The recursion theorem.''' Given a set ''X'', an element ''a'' of ''X'' and a function ''f'':''X''->''X'', then there is a unique function ''F'':'''N'''->''X'' such that

:''F''(0)=''a'', and

:''F''(''n''+1)=''f''(''F''(''n''))   for any [[natural number]] ''n''>0.

''[A proof of the recursion theorem from set theory is needed]''

Line 34:

The natural numbers can be defined as the smallest set satisfying the definition.

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

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

Line 45:

1. Are we done yet? If so, return the results.<br>

2. If not, simplify the problem and send it to 1.<br>

Virtually all [[programming language]]s 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 program can be transformed into an interative program 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]].

Line 50 ⟶ 52:

Such languages generally make [[tail recursion]] as efficient as iteration, letting programmers express other repetition structures (such as [[Scheme programming language|Scheme's]] <code>map</code> and <code>for</code>) in terms of recursion.

Recursion is deeply embedded in the [[theory of computation]], with the theoretical equivalence of [[recursive functionsfunction]]s and [[Turing machine]]s at the foundation of ideas about the universality of the modern computer.

See also:

* [[Recursion]]

* [[Self-reference]]

* [[Primitive recursive function]]