Design patterns for converting recursive algorithms to iterative ones

Question

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.

Welloff

Check out Eric Lippert's awesome series on Recursion: blogs.msdn.com/ericlippert/archive/tags/Recursion/… (Starts at Part Zero.) – Lawgiver

Well my mind just melted. – Isoelectronic

Answer 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.)

Schott

+1 for realizing that when you want to eliminate recursion you most likely want to avoid the stack in the first place. – Januarius

link to 'blog entry' doesnt seem to exist anymore. please update it – Basenji

Link still works (redirects) for me, but updated like is lorgonblog.wordpress.com/2008/06/07/catamorphisms-part-seven – Schott

BDotA: A tail call is when the return statement is a call to another function. For example, a recursive version of factorial(x) might have return x*factorial(x-1) somewhere in it. That's not a tail-call. Instead, that could be converted to return factorial(state*x, x-1), where state is the value so far. After all return statements are converted to calls, each return that is a tail call can be converted to state = state*x; x = x-1; goto start; In practice, you wouldn't need a goto because you'd use a while loop. – Cardinalate

@Brian: The link + redirect is now broken – Aileneaileron

Answer 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)

Noeminoesis

if you use a stack to eliminate recursion, all you're doing is instead of using the programming language's stack you are using your own custom stack, correct? Doesn't that defeat the purpose? – Januarius

yes, i'd ask why the poster wantd s general purpose algorithm since this is really the only one – Johnsson

@ldog: Does that defeat the purpose? No, not really. The program's stack is severely limited in size, whereas a user implemented stack would most likely be allocated on the free store, where there is a lot more room. I would think that lack of room on the stack is the most likely reason for converting from recursion to iteration, and this solves that problem. (Yes I realize this is 2 years old, but a recent question just linked to it) – Juliennejuliet

@Januarius There are also times when you need to convert an algorithm to a language that doesn't support recursion (i.e. OpenCL). – Henderson

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

Tbilisi

Answer 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;

Guinn

What about the case of branching calls, e.g. you recurse twice per call, e.g. tree traversal - is there a technique to do that? or have to use stack approach? – Selfregard

No, in that case you have to use general recursion, because after the first call you will have to return to the caller and then later do the second call. Of course you can replace general recursion by iteration and a stack. – Guinn

Answer 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...)

Tracery

Answer 6

I generally start from the base case (every recursive function has one) and work my way backwards, storing the results in a cache (array or hashtable) if necessary.

Your recursive function solves a problem by solving smaller subproblems and using them to solve the bigger the instance of the problem. Each subproblem is also broken down further and so on until the subproblem is so small that the solution is trivial (i.e. the base case).

The idea is to start at the base case(or base cases) and use that to build the solution for larger cases, and then use those to build even larger cases and so on, until the whole problem is solved. This does not require a stack, and can be done with loops.

A simple example (in Python):

#recursive version
def fib(n):
     if n==0 or n==1:
             return n
     else:
             return fib(n-1)+fib(n-2)

#iterative version
def fib2(n):
     if n==0 or n==1:
             return n
     prev1,prev2=0,1 # start from the base case
     for i in xrange(n):
             cur=prev1+prev2 #build the solution for the next case using the previous solutions
             prev1,prev2=cur,prev1
     return cur

Elsey

Answer 7

One pattern is Tail Recursion:

A function call is said to be tail recursive if there is nothing to do after the function returns except return its value.

Wiki.

Earley

-1 for not being an answer to the general question of how to transform a recursive problem to an iterative problem ( which is, in effect, how to transform a recursive problem into a tail recursive problem ), and because the out-of-context quote is not very clear ( a function X is in a tail position in a function Y if function Y does nothing after the call to X except return the result of that call; a function is tail recursive if all recursive calls in it are in tail positions ) – Tabulate