Asignación de memoria en llamadas recursivas de C ++

Question

Tengo problemas para asignar y desasignar mi memoria en un programa recursivo de C ++. Entonces, sin usar una solución de administración de memoria automática, me pregunto si alguien puede ayudarme a resolver la pérdida de memoria que estoy experimentando.

El siguiente código explica esencialmente el problema (aunque es un ejemplo artificial, corrija cualquier error o simplificación que haya cometido).

Una clase de número para mantener el valor de un número:

class Number {
    public:
        Number() { value = 1; };
        Number& operator + (const Number& n1) const {
            Number result = value + n1.value;
            return result;
        };
        int value;
};

Dos funciones para realizar la recursión:

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);
}

Como se puede ver, la memoria asignada en la función de recuperación se ha filtrado, pero no estoy seguro de dónde puedo liberar esta memoria según la naturaleza de la recursión.

Answer 1

El problema está aquí:

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

Está devolviendo una variable local ( resultado ) por referencia, y eso es un gran NO-NO. Las variables locales se asignan en la pila, y cuando la función sale, las variables desaparecen. Devolver una referencia a una variable local es devolver un puntero a la pila que ahora se usa para otra cosa, y eso va a causar mucha maldad.

Lo que debes hacer es devolver por valor (solo cambia el tipo de devolución de Number & amp; a Number ). Asegúrese de tener un constructor de copias adecuado o de que el constructor de copias generado automáticamente por el compilador se adapte a sus necesidades. Esto significa que cuando operator + devuelve, hace una copia (que a menudo se puede optimizar), y como no hay punteros o referencias involucradas, no puede obtener un valor de retorno dañado.

Para corregir la pérdida de memoria, puede usar punteros inteligentes como boost :: shared_ptr . Alternativamente, elimine los punteros de zanja y la memoria dinámica, y simplemente devuelva los resultados por valor de recurse () .

Answer 2

Para empezar, no veo por qué asignas la memoria en el montón:

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;
}

Al asignar solo en la pila, se garantiza que las variables se limpiarán cuando la función regrese.

De lo contrario, creo que tendrías que usar algún tipo de puntero inteligente.

Answer 3

Por lo tanto, veo otros tres problemas en el código además de devolver la dirección de una variable local que Adam Rosenfield señaló.

Primero, tu función resursiva nunca terminará. En algún momento en recurse (), debe verificar un valor que haga que no vuelva a llamar a recurse () y simplemente regresar. Esa es una parte fundamental de la recursión. El argumento pasado, v1, tampoco se está utilizando.

Segundo, el operador + () no funciona realmente. No hay una manera de asignar un int a un objeto Number ().

En tercer lugar, en la pantalla principal, se pasa algo que se llama resultado que nunca se declara.

Olvidando esos errores, asumo que desea asignar todos los objetos en el montón para evitar un desbordamiento de pila, donde esta función repetirá muchas veces o el objeto real utilizado es mucho más grande que el Número. En ese caso, al asignar la variable de retorno en el montón dentro de recurse (), está obligando a la persona que llama a eliminar el objeto devuelto. Así que después de las llamadas a recurse () en recurse () y main () tendrías que eliminar el valor devuelto. La convención para indicar que la persona que llama es devolver un puntero en lugar de una referencia. Así que recurse () y main () se verían así:

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;
}

Nota: Todo lo que se calcula en realidad es absurdo. No sé cuáles son las intenciones, pero es algo que funciona.

Answer 4

¿Hay alguna razón por la que está asignando dinámicamente la memoria?

Number recurse(const Number& v1) {
    Number result;
    Number one;
    retun result + recurse(one);
}

También noté que no está utilizando el valor v1

Pero el gran error es que la recursión tiene una cláusula de escape NO .
Esto es en efecto una recursión infinita que básicamente se quedará sin memoria.

Answer 5

Los punteros inteligentes son tus amigos. Haga una lectura rápida en auto_ptr como mínimo.

También, lea el comentario de Adam Rosenfield sobre su otro problema (devolviendo una referencia a un valor que ya no existe).