← Volver a los ejercicios

pendientes: lineal frente a cola

Dos funciones que calculan lo mismo, se llaman a sí mismas las dos, y generan procesos distintos. La diferencia no está en el resultado ni en cuántas vueltas dan: está en qué queda esperando mientras la llamada vuelve. Aquí corren a la vez.

1. Elija el par y prediga

En el punto más hondo, ¿cuántos marcos quedan abiertos al tiempo en la columna izquierda?

2. Ejecute las dos a la vez

— recursión lineal

— recursión de cola

Paso 0 de 0
La pila de cada columna muestra los marcos abiertos en ese instante, el más nuevo arriba y numerado por hondura. Cada marco dice qué tiene adentro: los de abajo esperan su multiplicación, y el de arriba está entrando o acaba de recibir el valor del que se cerró. A la derecha la caja es siempre la misma, con borde doble: la llamada nueva reemplaza a la anterior y el marco dice a quién.

3. Lo que se lleva de aquí

Las dos columnas terminan en el mismo valor y dan más o menos las mismas vueltas. La izquierda llega a tener n + 1 marcos abiertos al tiempo; la derecha, uno, siempre. Eso es el espacio, y es lo que se acaba en factorial(100000) y no en fact(100000).

Eso tiene un nombre: la de la derecha es recursión de cola. La llamada recursiva es lo último que hace el cuerpo, sin nada alrededor esperando su resultado, así que no hace falta acordarse de nada mientras vuelve. Un proceso iterativo escrito con una función recursiva.

Lo que hay que saber reconocer es cuándo una función es de cola y cuándo dejó de serlo sin que se note. Ese es el siguiente ejercicio.

Ir a cola: cuál sigue siendo de cola →