Memory Allocation in Recursive C++ Calls

Question

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?

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.