Design patterns for converting recursive algorithms to iterative ones

Are there any general heuristics, tips, tricks, or common design paradigms that can be employed to convert a recursive algorithm to an iterative one? I know it can be done, I'm wondering if there are practices worth keeping in mind when doing so.

Solution 1:

You can often entirely preserve the original structure of a recursive algorithm, but avoid the stack, by employing tail calls and changing to continuation-passing, as suggested by this blog entry. (I should really cook up a better standalone example.)

Solution 2:

A common technique that I use where I'm on the process of replace a recursive algorithm by an iterative one is generally to use a stack, pushing the parameters that are being passed to the recursive function.

Check the following articles:

• Replacing Recursion With a Stack
• Stacks and Recursion Elimination (pdf)

Solution 3:

A common practice is to manage a LIFO stack that keeps a running list of what "remains to be done", and to handle the whole process in a while loop which continues until the list is empty.
With this pattern, what would be a recursion call in the true recursion model is replaced by
- a pushing of current (partially finished) task's "context" onto the stack,
- a pushing of the new task (the one which prompted recursion) onto the stack
- and to "continue" (i.e. jump to the beginning of) the while loop. Near the head of the loop, the logic pops the most recently inserted context, and starts work on this basis.

Effectively this merely "moves" information which would have otherwise been kept in nested stackframes on the "system" stack, to an application-managed stack container. It is an improvement however, for this stack container can be allocated anywhere (the recursion limit is typically tied to limits in the "system" stack). Therefore essentially the same work gets done, but the explicit management of a "stack" allows this to take place within a single loop construct rather than recursive calls.

Solution 4:

Often general recursion can be replaced by tail recursion, by collecting partial results in an accumulator and passing it down with the recursive call. Tail recursion is essentially iterative, the recursive call can be implemented as a jump.

For example, the standard general recursive definition of factorial

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

can be replaced by

 factorial(n) = f_iter(n, 1)

and

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

which is tail recursive. It is the same as

a = 1;
while (n != 0) {
    a = n * a;
    n = n - 1;
}
return a;

Solution 5:

Have a look at these links for performance examples

Recursion VS Iteration (Looping) : Speed & Memory Comparison

and

Replace Recursion with Iteration

and

Recursion vs Iteration

Q: Is the recursive version usually faster? A: No -- it's usually slower (due to the overhead of maintaining the stack)

  Q: Does the recursive version usually use less memory?
  A: No -- it usually uses more memory (for the stack).

  Q: Then why use recursion??
  A: Sometimes it is much simpler to write the recursive version (but

we'll need to wait until we've discussed trees to see really good examples...)