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.

Answer 1

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.

Answer 2

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

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.

Answer 4

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
• Using a Stack to Simulate Recursion
• Stacks and Recursion Elimination (pdf)

Answer 5

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

Answer 6

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;

Answer 7

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

Answer 8

The book "Structure and Interpretation of Computer Programs" tells about the difference between recursive process and iterative process...

They have also gives as exercise, this problem...

A function f is defined by the rule that

f (n) = n if n<3 
f (n) = f (n - 1) + 2f (n - 2) + 3f (n - 3) if n>= 3

But, I don't know how to approach the problem...