Recursion VS memory allocation
- by Vladimir Kishlaly
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?
