Recursion versus manual stacks - Which is preferred in which case?

Question

A recursive program creates a stack internally, and causes the users to write less code.

Are there any cases where recursion is actually preferred over manual stacks for the reason other than mentioned above?

EDIT 1:

In what way is dynamic memory allocation more "expensive" than the allocations on the heap by a recursive program?

Answer 1

The main reason, which I think you're alluding to when you say "less code", is clarity and simplicity of design. In a language with features like local variables and automatic storage, it is infinitely more natural to use those features than to structure everything into home-rolled stacks. (After all, why use functions at all? Why not write your entire program using if/else and while as your only control structures?)

Another consideration is performance, especially in multithreaded environments. Recursion — depending on the language — is likely to use the stack (note: you say "creates a stack internally", but really, it uses the stack that programs in such languages always have), whereas a manual stack structure would require dynamic memory allocation, which frequently has a noticeable performance penalty — not to mention the added complexity of making sure that you release all that memory when you (say) encounter an exception.

Answer 2

I mostly agree with @ruakh's answer. I would only add that using the system stack has a lot of overhead (you are actually pushing a lot more state than you need every time you recurse) and might cause stack overflows for very deep (but bounded) recursion, which you may be able to avoid by using an explicit stack and only pushing the state that you need.

Answer 3

USING STACKS EXTERNALLY

vector<int> Solution::inorderTraversal(TreeNode* A) {
vector<int> res;
stack<TreeNode* > st;
TreeNode* root=A;
while(true)
{
    if(root==NULL)
    {
        if(st.empty())
        break;
        root=st.top();
        st.pop();
        res.push_back(root->val);
        root=root->right;


    }
    else
    {

        st.push(root);
        root=root->left;
    }
}
return res;

}

USING RECURSION

void inorder(struct node* root)

but here we see that usage of stacks externally saves a lot of processing time and hence the external stack approach is quicker.