Way to go from recursion to iteration

Question

I've used recursion quite a lot on my many years of programming to solve simple problems, but I'm fully aware that sometimes you need iteration due to memory/speed problems.

So, sometime in the very far past I went to try and find if there existed any "pattern" or text-book way of transforming a common recursion approach to iteration and found nothing. Or at least nothing that I can remember it would help.

• Are there general rules?
• Is there a "pattern"?

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.