Concept:Recursion removal
== Headline ==
An algorithm for transforming recursive into iterative functions
== Illustration ==
Each recursive function can be transformed into an equivalent non-recursive function, subject to using [[iteration|]] constructs and possibly
extra data structures for simulating the [[call stack]]. Depending on programming language and form of recursion, different algorithms can be applied.
Consider the following recursive formulation of [[factorial]]:
<syntaxhighlight lang="java">
public static long factorial(int n) {
if (n <= 1)
return 1;
else
return n * factorial(n - 1);
}
</syntaxhighlight>
There are various iterative forumulations of [[factorial]]. There are different approaches towards deriving an iterative formulation from a recursive.
The following example illustrates how [[single recursion]] can be transformed into iteration while a [[stack]] is used to keep track of variables for
each call frame.