Recursion VS memory allocation

Question

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;
    root.printValue();
    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?

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 05 '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 05 '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 05 '14 at 12:56
quite an outright duplicate of [Are there advantages for using recursion over iteration - other than sometimes readability and elegance?](http://programmers.stackexchange.com/questions/242889/are-there-advantages-for-using-recursion-over-iteration-other-than-sometimes-r) and of [What are the advantages of recursion compared to iteration?](http://programmers.stackexchange.com/questions/234962/what-are-the-advantages-of-recursion-compared-to-iteration) — gnat, Jun 05 '14 at 13:03
@Phoshi - and in the "real world" that I live in, there are datasets that will blow your heap. What's your point? — kdgregory, Jun 05 '14 at 13:14
@kdgregory: The stack is generally a heck of a lot easier to blow than the heap, and it's a lot more awkward to expand your stack size? — Phoshi, Jun 05 '14 at 13:21
@Phoshi - while everything you say is correct, if I saw an iterative tree traversal in real-world code I would ever-after consider the developer completely incompetent. Because the only way that a tree can blow even a small stack is if it's pathologically unbalanced. In which case either (1) the developer should have figured out why it's unbalanced, or (2) the developer should have realized that a tree was an inappropriate data structure. — kdgregory, Jun 05 '14 at 13:48
@kdgregory: Depends on what your tree is representing. I've been working with parse trees recently, so arbitrary trees are on my mind. — Phoshi, Jun 05 '14 at 14:10
@Phoshi Couldn't you use continuation passing style to TCO both calls? `...; preorderTraversal(root.getLeft(), () => preorderTraversal(root.getRight());` — Doval, Jun 05 '14 at 14:49
@Doval: If that's idiomatic in your language and team I think that's probably a better choice, but if your team doesn't have a background in functional programming that might be more confusing than an iterative approach. — Phoshi, Jun 05 '14 at 15:12

score 0 · Answer 1 · answered Jun 05 '14 at 12:36

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.

Recursion VS memory allocation

1 Answers1