Recursion VS memory allocation
Posted
by
Vladimir Kishlaly
on Programmers
See other posts from Programmers
or by Vladimir Kishlaly
Published on 2014-06-05T09:31:39Z
Indexed on
2014/06/05
9:42 UTC
Read the original article
Hit count: 462
recursion
|memory-usage
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?
© Programmers or respective owner