← Volver a los ejercicios

contar: la pila que crece y encoge

Una función recursiva hace su trabajo en dos viajes: baja hasta el caso base y vuelve. Lo que importa aquí no es el resultado sino qué queda esperando en cada viaje. Cada caja de la pila es una multiplicación que no se puede hacer todavía.

1. Antes de ejecutar, prediga

Llamada de partida:
¿Cuántas multiplicaciones va a hacer?

2. Ejecute y mire la pila

Paso 0 de 0
El contador del else sube en la bajada, uno por llamada. El caso base se usa una sola vez. Fíjese en qué paso la pila llega a su punto más alto y compárelo con n.

3. Lo que se lleva de aquí

Las multiplicaciones son n, y eso es el tiempo. Pero en el punto más hondo hay también n cajas esperando, y eso es el espacio: la función se acuerda de n cosas a la vez antes de resolver la primera.

Los dos números coinciden aquí, y por eso es fácil confundirlos. El siguiente ejercicio los separa.

Ir a reducir: la expresión que se reemplaza →