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?

Appling

If your recursion does not exceed the stack size then you are only using the call stack and not the heap. – Applicator

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.

Miramontes

The tradeoff you make for the performance of using the system stack is that you're typically much more limited for the depth of recursion with the system stack than with a stack data structure on the heap, since the heap is so much bigger. – Dossier

whereas a manual stack structure would require dynamic memory allocation, which frequently has a noticeable performance penalty That's a point. But the repeated function calls isn't a performance penalty? Isn't it greater than the manual memory allocations? – Appling

@SethCarnegie: Yes, absolutely, good point. And running out of heap memory is, on many platforms, better handle-able than overflowing the stack. Since the question was strictly about reasons to use recursion, I didn't mention these things, but maybe I should have, anyway, just for completeness? – Miramontes

@AnishaKaul: As always, if performance matters to this extent, then you need to test it on the platforms you care about; but speaking generally -- if you use a linked-list as your stack, then I'd expect the dynamic memory allocations to be more expensive than repeated function calls, but if you use a dynamically resizeable array and add/remove elements from the end, then you can quite likely reduce the number of dynamic memory allocations to the point where it's quite cheap. The problem with that, however, is that if your goal is to eliminate repeated function calls, then, what, are you going – Miramontes

In what can dynamic memory allocation be "expensive"? Isn't is only about allocating and deallocating memory? – Appling

@AnishaKaul: Yes -- and that's expensive. The system needs to keep track of what memory is currently allocated (so that it doesn't allocate the same memory twice), and it needs to do everything in a thread-safe way, and so on. There's a lot of overhead. – Miramontes

How to decide then which is more expensive out of the two? Should it be a seperate question? – Appling

@AnishaKaul: Testing. Always testing. If you're curious -- I just wrote a relatively simple C program that builds a linked-list [1,2,3,...,500] and calls one of three functions to compute 1 + (1 XOR (2 + (2 XOR (3 + (3 XOR (4 + ... (500 + 500)...)))))). One function is just straightforward recursion; one function builds a linked list that's the reverse of its argument, then iterates over that list; and one function builds a dynamically-resizing array and populates it with its argument, then iterates backward over the array. (continued) – Miramontes

@AnishaKaul: For each version, I called the function 100,000 times in a small loop that just called the function and confirmed that it returned the correct value (110592). For the first function, that took about 0.3 seconds. For the second function, it took about 9 seconds. For the third function, it took about 0.9 seconds. So on my system, the recursive function was about three times faster than the dynamically-resizing-array-building function, which was about ten times faster than the linked-list-building function. (Which is about what we'd expect.) – Miramontes

@AnishaKaul: By the way, if you want to play around with this, and are willing to temporarily post your e-mail address, I can send you the source-code for the tests I just ran, so you can play around with them yourself. (If you know C.) – Miramontes

@Miramontes Very Interesting. Have you tested how fast it is when you use a fixed sized array (allocated on the system stack) as your stack? Sometimes it is possible to upper-bound the depth of the recursion. – Tartu

@SethCarnegie Why the heap is bigger? Doesn’t heap share the same address space as the stack? If I can allocate 4 GB stack structure in heap, why can’t the call stack grow 4 GB down? – Headed

for more information on this question, you can also visit this link. – Boutte

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.

Morten

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.

Nether

void inorder(struct node* root) {if(root!=NULL) {inorder(root->left);cout<<root->val;inorder(root->right);} } – Nether