Recursion vs iteration with regards to memory usage

Question

Suppose I have a recursive as well as an iterative solution (using a stack) to some problem e.g. preorder traversal of a binary tree. With current computers, memory-wise, is there an advantage to using the recursive solution over the iterative version or vice versa for very large trees?

I'm aware that for certain recursive solutions where sub-problems repeat, there are additional time and memory costs if recursion is used. Assume that this is not the case here. For example,

preOrder(Node n){
    if (n == null) return;
    print(n);
    preOrder(n.left);
    preOrder(n.right);
}

vs

preOrder(Node n){
    stack s;
    s.push(n);
    while(!s.empty()){
        Node node = s.pop();
        print(node);
        s.push(node.right);
        s.push(node.left);
    }
}

Solution

If there is a risk of stack overflow (in this case, because the trees are not guaranteed to be even semi-balanced), then a robust program will avoid recursion and use an explicit stack.

The explicit stack may use less memory, because stack frames tend to be larger than is strictly necessary to maintain the context of recursive calls. (For example, the stack frame will contain at least a return address as well as the local variables.)

However, if the recursion depth is known to be limited, then not having to dynamically allocate can save space and time, as well as programmer time. For example, walking a balanced binary tree only requires recursion to the depth of the tree, which is log₂ of the number of nodes; that cannot be a very large number.

As suggested by a commentator, one possible scenario is that the tree is known to be right-skewed. In that case, you can recurse down the left branches without worrying about stack overflow (as long as you are absolutely certain that the tree is right-skewed). Since the second recursive call is in the tail position, it can just be rewritten as a loop:

void preOrder(Node n) {
    for (; n; n = n.right) {
        print(n);
        preOrder(n.left);
        n = n.right;
}

A similar technique is often (and should always be) applied to quicksort: after partitioning, the function recurses on the smaller partition, and then loops to handle the larger partition. Since the smaller partition must be less than half the size of the original array, that will guarantee the recursion depth to be less than log₂ of the original array size, which is certainly less than 50 stack frames, and probably a lot less.

Comments

[Gene]

Good answer, but you could also point out that in the OP's example a good compiler will optimize the second recursive (tail) call to a loop, so only left children require stack frames. In that case, right-skewed trees will be searched in constant space by the recursive code and linear space by the explicit stack code. The moral is that details of implementation and compilation system matter.

[rici]

@gene: Originally, I had a discussion about the correctly tail-call-optimized quicksort algo, but I deleted it because it was getting off-topic. It's hard to do TCO with C++ and while I think gcc will find the optimization in this simple case, there are no guarantees. Since you can't know that the compiler will TCO a given function, robust code shouldn't rely on it. You could write the tail call as a loop and leave the non-TC recursion as is, which would work nicely for skewed trees or q-s; if I get ambitious I'll add the hybrid option.

[Frank Ibem]

Could you show me what the tail-call-optimized version looks like?

[rici]

@frank: The compiler will do the TCO (or not, depending on its mood) so there is no "tail-call-optimized" version. To optimize your iterative solution, nktice that you push and the end of the loop and then immediately pop, so you could just set n = n.left instead.