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.
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.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.