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

Filed under:
|

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

Related posts about recursion

Related posts about memory-usage