Way to go from recursion to iteration

by

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.

More Related Contents:

  1. What is a lambda (function)?
  2. Can every recursion be converted into iteration?
  3. What is recursion and when should I use it?
  4. Why should recursion be preferred over iteration?
  5. Recursion or iteration?
  6. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  7. SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process
  8. What is tail call optimization?
  9. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  10. Determining complexity for recursive functions (Big O notation)
  11. Tower of Hanoi: Recursive Algorithm
  12. What is referential transparency?
  13. recursion versus iteration
  14. “application: not a procedure” in binary arithmetic procedures
  15. What is a Y-combinator? [closed]
  16. Can all iterative algorithms be expressed recursively?
  17. Is there a difference between foreach and map?
  18. recursive variadic template to print out the contents of a parameter pack
  19. Multidimensional array iteration
  20. Is a Recursive-Iterative Method Better than a Purely Iterative Method to find out if a number is prime?
  21. Recursion vs loops
  22. jQuery recursive iteration over objects
  23. Is finding the equivalence of two functions undecidable?
  24. What are the lesser known but useful data structures?
  25. What is a Lambda?
  26. Examples of Recursive functions [closed]
  27. Hash Code and Checksum – what’s the difference?
  28. Converting EBNF to BNF
  29. What does “Overflow evaluating the requirement” mean and how can I fix it?
  30. Memory efficient power set algorithm

Leave a Comment