Recursion: Difference between revisions

Revision as of 14:22, 24 May 2002

Revision as of 14:07, 28 May 2002

Line 18:

= 3 * 2 * 1 * 1

= 6

Another example is the definition of [[Fibonacci number|Fibonacci numbers]].

In [[set theory]] there is a theorem guaranteeing that such functions exist.

Line 43 ⟶ 45:

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

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

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

Common method of the simplification is to divide the problem into subproblems. Such programming technique is called ''divide-et-impera'' and is a fundamental part of [[dynamic programming]].

Virtually all [[programming language|programming languages]]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]].

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 programming language|Scheme's]] <code>map</code> and <code>for</code>) in terms of recursion.

Line 55 ⟶ 59:

See also:

* [[Recursion]]

* [[Self-reference]]

* [[Primitive recursive function]]