Memory Allocation in Recursive C++ Calls

Question

Hi,

I'm having problems allocating and deallocating my memory in a recursive C++ program. So without using an automatic memory management solution, I wonder if anyone can help me resolve the memory leak I am experiencing.

The following code essentially explains the problem (although it's a contrived example, please correct any mistakes or simplifications I've made).

A number class to hold the value of a number:

class Number
{
    public:
        Number() { value = 1; };

        Number& operator + (const Number& n1) const
        {
            Number result = value + n1.value;
            return result;
        };

        int value;
};

Two functions to perform the recursion:

Number& recurse(const Number& v1)
{
    Number* result = new Number();

    Number one = Number();
    *result = *result + recurse(one);

    return *result;
}

int main(...)
{
    Number answer = Number();
    answer = recurse(result);
}

As you can see the memory allocated in the recurse function is leaked, but I'm not sure where I can free up this memory from based on the nature of the recursion?

Thanks,

Dan

Answer 1

The problem is here:

Number& operator + (const Number& n1) const
{
    Number result = value + n1.value;
    return result;
};

You're returning a local variable (result) by reference, and that's a big NO-NO. Local variables are allocated on the stack, and when the function exits, the variables are gone. Returning a reference to a local variable is returning a pointer into the stack that's now being used for something else, and that's going to cause lots of badness.

What you should instead do is return by value (just change the return type from Number& to Number). Make sure you have an appropriate copy constructor, or that the compiler's automatically generated copy constructor suits your needs. This means when operator+ returns, it makes a copy (which can often by optimized away), and since there's no pointers or references involved, you can't get a corrupted return value.

To fix your memory leak, you can use smart pointers such as boost::shared_ptr. Alternatively, ditch pointers and dynamic memory altogether, and just return your results by value from recurse().

Answer 2

I don't see why you're allocating the memory on the heap to begin with:

Number& recurse(const Number& v1)
{
    Number result;

    Number one;

    // I assume there is a step here to determine if the recursion should stop

    result += recurse(one);

    return result;
}

By allocating only on the stack you're guaranteed that the variables will be cleaned up when the function returns.

Otherwise I think you'd have to use some sort of smart pointer.

Answer 3

Smart pointers are your friend. Do a quick read-up on auto_ptr at the very least.

Also, read Adam Rosenfield's comment on your other problem (returning a reference to a value that doesn't exist anymore).

Answer 4

So I see three other problems in the code other than returning the address of a local variable that Adam Rosenfield pointed out.

First, your resursive function will never end. At some point in recurse(), you must check for a value that causes it to not call recurse() again and just return. That is a fundamental part of recursion. The argument passed, v1, is also not being used.

Second, the operator+() does not actually work. There is not a way to assign an int to a Number() object.

Third, in main you pass something called result which is never declared.

Forgetting those errors, I assume that you want to allocate all the objects on the heap to avoid a stack overflow, where this function will recurse many times or the actual object used is much larger than Number. In that case by allocating the return variable on the heap inside recurse() you are forcing the caller to delete the returned object. So after the calls to recurse() in recurse() and main() you would have to delete the returned value. The convention for indicating that to the caller is to return a pointer instead of a reference. So recurse() and main() would look something like this:

Number* recurse(const Number& v1)
{
    Number* result = new Number();

    Number one;
    if( v1.value >= 2 )
    {
     Number temp;
     temp.value = v1.value - 1;
     Number* partialResult = recurse( temp ); //capture the object to delete
     *result = *partialResult + one;
     delete partialResult;                    //delete the object
    }

    return result;
}

int main()
{   
    Number result;
    result.value = 15;

    Number *answer;
    answer = recurse(result);
    delete answer;
}

Note: Whatever recurse actually calculates is nonsensical. I don't know what the intentions are but it is just something that works.