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?
10
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.