Convert recursion to iteration

Question

I often use recursion. However, iteration is sometimes preferable since it can execute directly (in languages without special optimizations) with fewer issues in terms of memory and speed.

I want to transform functions that rely upon recursion to instead use iteration.

• Are there general rules?
• Is there a "pattern" for this transformation?

Answer 1

Usually, I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack. In fact, you are replacing the program stack by one of your own.

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

Note: if you have more than one recursive call inside and you want to preserve the order of the calls, you have to add them in the reverse order to the stack:

foo(first);
foo(second);

has to be replaced by

stack.push(second);
stack.push(first);

Edit: The article Stacks and Recursion Elimination (or Article Backup link) goes into more details on this subject.