Which approach is most popular in real-world examples: recursion or iteration?

For example, simple tree preorder traversal with recursion:

void preorderTraversal( Node root ){
    if( root == null ) return;
    preorderTraversal( root.getLeft() );
    preorderTraversal( root.getRight() );

and with iteration (using stack):

Push the root node on the stack
While the stack is not empty
    Pop a node
    Print its value
    If right child exists, push the node's right child
    If left child exists, push the node's left child

In the first example we have recursive method calls, but in the second - new ancillary data structure.

Complexity is similar in both cases - O(n). So, the main question is memory footprint requirement?

marked as duplicate by user40980, gnat, david.pfx, DougM, user53019 Jun 7 '14 at 23:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    No, the main question is how maintainable and readable the code is. And if you have a language that provides a stack, I would argue that adding your own stack decreases maintainability and readability. Although it might increase job security. – kdgregory Jun 5 '14 at 12:23
  • Actually, to go a little deeper: this example is recursive by nature; you have to do extra work to make it iterative. In the "real world," only an idiot or jerk would use the second approach. There are, however, a large number of cases where the problem can be solved equally well both ways. And in those cases, it depends on the mindset of the programmer; any responses you'd get are opinions. – kdgregory Jun 5 '14 at 12:26
  • @kdgregory: In the "real world", the recursive approach will blow your stack on deep enough trees, even in a tail-recursive language (due to not being able to TCO /both/ calls.) – Phoshi Jun 5 '14 at 12:56
  • 1
  • @Phoshi - and in the "real world" that I live in, there are datasets that will blow your heap. What's your point? – kdgregory Jun 5 '14 at 13:14

In the case of descending a recursive structure such as a tree, memory requirement is of the same order using either recursion or iteration (proportional to depth).

It's probably a bit cheaper to use iteration since you don't have to keep track of stack frames, and you also get the additional flexibility of being able to choose your maximum recursion depth (some languages have finite call stack size).

That being said, this is quite language-dependent as it depends on whether tail-recursion optimizations are available and whether stack frames are kept track of. In some languages, the recursive example can be optimized into the equivalent iterative form.

In general, for languages where iteration is possible, recursion costs at least as much memory as iteration.

Not the answer you're looking for? Browse other questions tagged or ask your own question.