¿Cómo la recursión hace que el uso de la memoria en tiempo de ejecución sea impredecible?

Citando de Code Complete 2,¿Cómo la recursión hace que el uso de la memoria en tiempo de ejecución sea impredecible?

int Factorial(int number) { 
    if (number == 1) { 
     return 1; 
    } 
    else { 
     return number * Factorial(number - 1); 
    } 
} 
Además de ser lento^[1] y haciendo el uso de la memoria de tiempo de ejecución impredecible^[2], la versión recursiva de esta rutina es más difícil entender que la versión iterativa, que sigue:
int Factorial(int number) { 
    int intermediateResult = 1; 
    for (int factor = 2; factor <= number; factor++) { 
     intermediateResult = intermediateResult * factor; 
    } 
    return intermediateResult; 
} 

Creo que la parte lenta es debido a los gastos generales de la función de llamadas innecesarias.

Pero, ¿cómo la recursión hace que el uso de la memoria en tiempo de ejecución sea impredecible?

¿No podemos predecir siempre cuánta memoria se necesitaría (como sabemos cuando se supone que la recursión termina)? Creo que sería tan impredecible como el caso iterativo, pero ya no.

Fuente

2010-11-02 Lazer

Tenga en cuenta que la recursividad PUEDE ejecutarse en tiempo constante SI el procedimiento usa recursividad final Y si el lenguaje admite la optimización de la llamada de cola. Busque "recursividad de la cola" si le interesa. – erjiang

Además, en algunas CPU como la función de Sparc, la sobrecarga de llamadas es muy baja. Y con algunos lenguajes de programación como Tcl, la función de llamada es en realidad más rápida que el código en línea (debido a cómo funciona el bytecompiler). – slebetman

Debido a que los métodos recursivos se llaman a sí mismos repetidamente, necesitan mucha memoria de pila. Como la pila está limitada, se producirán errores si se supera la memoria de la pila.

Fuente

2010-11-02 18:25:21 codymanix

eso es lo que yo pensaba, pero ¿por qué sería eso impredecible? – Lazer

Creo que solo significa "depende de un valor en tiempo de ejecución". La versión iterativa que puedo predecir siempre toma 8 bytes de la pila (o lo que sea necesario), mientras que no puedo "predecir" la recursiva, ya que depende del valor de 'number 'pasado en el tiempo de ejecución. Entonces, "impredecible" significa "no se puede predecir un valor constante en tiempo de compilación". – Brian

No sería predecible si no supiera cuántas veces se llama la función, ¿verdad? Si la función se llama a sí misma demasiadas veces, tendría un 'stackoverflow' =) – gideon

Si el nivel de recursión es demasiado profundo, soplará la pila de llamadas y consumirá mucha memoria en el proceso. Esto puede suceder si su number es un valor "lo suficientemente grande". ¿Puedes hacer algo peor que esto? Sí, si su función asigna más objetos con cada llamada de recursión.

Fuente

2010-11-02 18:36:04 darioo

¿No podemos siempre predecir cuánta memoria se necesitaría (como sabemos cuando se supone que la recursión termina)? Creo que sería tan impredecible como el caso iterativo, pero ya no.

No, no en el caso general. Consulte la discusión sobre el halting problem para obtener más información. Ahora, aquí está una versión recursiva de uno de los problemas allí expuestos:

void u(int x) { 
    if (x != 1) { 
     u((x % 2 == 0) ? x/2 : 3*x+1); 
    } 
}

Es incluso recursiva de cola. Como no puede predecir si esto terminará normalmente, ¿cómo puede predecir cuánta memoria se necesita?

Fuente

2010-11-04 02:09:28 ldav1s

¿Cómo la recursión hace que el uso de la memoria en tiempo de ejecución sea impredecible?

Respuesta

Cuestiones relacionadas