Hola, no entiendo del todo como calcular el consumo del stack en un procedimiento recursivo, estuve intentando analizar los ejemplos de las diapositivas y del examen de diciembre pero no entiendo bien cuándo cuenta o no.
Así es como lo pienso yo:
Por ejemplo: en el Segundo Ejemplo de la diapositiva:
Inicia con un elemento, el IP.
Para el paso base compara y salta, luego retorna por tanto el consumo(0) = 2 bytes
Para el recursivo, hace push AX y llama a fact(n-1), luego hace un Pop -> 4 bytes + consumo(n-1) . Bien, como muestra la solucion mas abajo
Luego no me cierra para el Tercer Ejemplo:
Carga en el stack el parametro y la IP del primer llamado (4 bytes)
Para el caso base: hace 2 pop y un push (quedando en 2 bytes), luego en fin: hace un pop y 2 push, por lo tanto el consumo es 4 bytes.
Paso recursivo: luego de los 2 pop y el push: 2 bytes. 2 push más y un call (8 bytes). Cuando vuelve hace 2 pop, y luego 1 pop y 2 push -> consumo = 6 bytes + consumo(n-1).
¿Qué me estoy perdiendo acá? Porque dice que debería ser 4 + consumo(n-1)
Tambien en el Cuarto ejemplo:
Carga en el stack el parametro y la IP del primer llamado (4 bytes).
Paso base: 3 Push (10 bytes) y luego en fin hace 3 pop, quedando en 4 bytes.
Paso Recursivo: 3 Push (10 bytes), luego hace un push, un Call y un Pop (12 bytes), luego los 3 pop, quedando en 6 bytes + consumo(n-1)
No me termina de cerrar ninguno sobre cómo calcularlo correctamente.. Alguien me tira una idea?
Muchas Gracias!
Ezequiel
Hola.
Me parece que estás mezclando las cosas, lo importante en estos ejercicios es cuanto se va acumulando en el stack, por lo que no tenés que tener en cuenta que pasa cuando volvés de la llamada recursiva, pues si pasa eso no se acumulan las llamadas recursivas.
Qué pasa cuando volvés de la llamada recursiva es usado para acomodar el stack, resultados, contexto y dirección de retorno deben acomodarse/retirarse de forma consistente con el protocolo de pasaje de parámetros.
Saludos, Gonzalo
Hola Gonzalo, gracias por tu respuesta
Entendí lo del paso recursivo, pero me sigue quedando la duda en el paso base.
¿Está bien que para calcularlo sume, además de los bytes correspondientes del caso base del procedimiento, los bytes de la llamada inicial?
Por ejemplo en el ejemplo del teórico, con la función factorial, el caso base sería una llamada directa con 0.
En el ejemplo Nº 3 (Diapositiva nº 7 de las rutinas recursivas) hace lo siguiente:
- push n
- call fact
- pop dx
- pop ax
- push dx
// Compara con 0, como es base salta y acomoda el stack
// Si freno acá, tendría un consumo de 2 bytes
- pop dx
- push bx
- push dx
// Termina, consumo base de 4 bytes
En la diapositiva 8, dice: "consumo(0)=4"
Ahora, en el ejemplo Nº 4 (Diap. 9) hace lo siguiente:
- push n
- call fact
- push bp
- push ax
- push dx
// Compara con 0, como es base salta y acomoda el stack
// En este momento tiene un consumo de 10 bytes (como indica en la diap. 10)
- pop dx
- pop ax
- pop bp
// Termina la ejecución, habiendo consumido 4 bytes finalmente, no 10 como dice en la diapositiva siguiente
Es ahí donde me mareo... Si es el paso base, debería terminar la ejecución no?
En el paso recursivo sí paro de contar el consumo en el momento que invoca la funcion recursiva.
Sí, pero a lo que apunta es al máximo consumo, antes de vaciar el stack.
Saludos, Gonzalo.
Impecable, gracias!
Saludos, Ezequiel