Returning 'Destructable' objects from Recursive Function

[sid78669]

I recently had an assignment for an advanced coding class where I was to create a Binary tree from inorder and preorder traversals. I first started out by creating my ADT for binary trees and working with that to create a new tree. The way I worked it was that I started by storing inorder traversal in an array and preorder in a queue and then I went through dividing the array into smaller arrays and passing it to the function again, recursively. The base case was when there was only one element in the array, i.e. a leaf. and this was returned by the function.

The problem I encountered was that my tree had a destructor and was being destroyed before the function could send it back since it was declared as a local variable for the setupFunction. I tried everything from pointers to references but everytime the subtree was corrupted.

I did end up converting the recursion into a while loop. But my question is, if you are trying the return a custom ADT from a recursive call, how should you do it?

[alwaysLearning0]

Passing by reference/pointer should work, are you sure your are passing by reference, not creating a local copy?

if you post some code, then it will be much more helpful to figure out why recursion is not working with reference.

[sid78669]

I think the problem might be the local copy thing. I'll post some code after Thursday, thats when the assignment is due and I seriously don't want to breach the Academic policy ;)

[arkoenig]

Your poll does not allow me to select more than one alternative. I would like to select #3 and #4 but I can't.

[sid78669]

yes, I think I should have made it multi select.

[arkoenig]

And then there's the issue that maybe the most straightforward thing to do is to unwind the recursion part but not all the way.

For example:

void traverse(Tree* p)
{
    if (p) {
        work_on(p);
        traverse(p->left);
        traverse(p->right);
    }
}

The second call to traverse is a tail recursion, which implies that it is probably a worthwhile optimization to rewrite it as an iteration:

void traverse(Tree* p)
{
    while (p) {
        work_on(p);
        traverse(p->left);
        p = p->right;
    }
}

The remaining call to traverse is not a tail recursion, so it is much harder to rewrite the code to eliminate it. It may well be that it is not worthwhile to do so.