Recursion (computer science): Difference between revisions

Revision as of 23:18, 13 February 2006

Revision as of 06:07, 28 February 2006

Line 5:

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 algorithm|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 language]]s in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer (for most languages on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many architectures, by using a [[Stackcall (computing)|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.

Line 49:

end function'''

In this particular example the iterative implementation is slightly faster in practice than the recursive one. (Note that an even faster implementation for the ''Factorial'' function is that of using a [[lookup table]].) There are other types of problems that seem to have an inherently recursive solution, i.e. they need to keep track of prior state. One example is [[tree traversal]], which is possible to implement iteratively with the help of a [[Stack (data structure)|stack data structure]], but the need for the stack arguably defeats the purpose of the iterative solution. Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, thread stacks are often much smaller than memory available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms.

===recursion vs. iteration ===

While recursion can simplify the solution of a problem, often resulting in shorter, more easily understood source code, it is often less efficient, in terms of both time and space, than iterative solutions. There are some methods to convert recursive algorithm into an iterative algorithalgorithm using a loop and branching structure.

==Recursive functions==