CODEWITHSUNDEEP
algorithmrecursioniteration
Frank Ibem
Frank Ibem

Reputation: 834

Recursion vs iteration with regards to memory usage

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);
    }
}

Upvotes: 13

Views: 12750

Answers (1)

rici
rici

Reputation: 241681

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 log2 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 log2 of the original array size, which is certainly less than 50 stack frames, and probably a lot less.

Upvotes: 13

Related Questions