← Volver a los ejercicios

reversa: la concatenación que queda pendiente en cada marco

El caso recursivo escribe reversa(xs) ++ List(x), y el ++ no puede correr hasta que la llamada de la izquierda devuelva. Así que cada marco anota su ++ List(x) y se queda esperando: la pila baja hasta Nil con todas las concatenaciones sin resolver y las resuelve de adentro hacia afuera al volver. Avance paso por paso y mire la pila: la profundidad dice cuántos marcos están abiertos y la operación pendiente, qué dejó cada uno sin hacer.

1. La función y la pila

paso 0 de 0
■ marco abierto, esperando a la llamada de adentro ■ marco que está corriendo ■ marco que ya resolvió su concatenación
última concatenación: –
celdas que ++ ha recorrido: 0
reversa(List()) = –

La línea 1 cuenta las llamadas, la 2 el caso base, la 3 los marcos que salen con una concatenación pendiente y la 4 los que devuelven. Con una lista de tres elementos hay cuatro llamadas, porque la última recibe Nil.

2. Lo que se lleva de aquí

La recursión es lineal: cada marco hace una sola llamada y espera. Lo que la hace distinta de una suma recursiva es lo que queda pendiente. En x + sumar(xs) la operación que espera es una suma de enteros y cuesta lo mismo en cualquier marco. En reversa(xs) ++ List(x) la operación que espera es una concatenación, y ++ recorre la lista de su izquierda nodo por nodo para copiarla. El marco más profundo concatena sobre List() y no recorre nada; el más externo concatena sobre una lista de n - 1 elementos.

Sumar esos recorridos da 0 + 1 + ... + (n - 1), que es n(n - 1)/2: el contador de celdas llega a 3 con tres elementos y a 6 con cuatro. De ahí el O(n²) del deck, con una lista que solo tiene n elementos. Cambie la lista con los botones y compare el contador.

Las concatenaciones se resuelven en el orden inverso al que quedaron anotadas, porque la pila se desarma por donde se armó. El primer elemento de la lista original es el último que se concatena, y por eso termina de último en el resultado. Bajar el costo pide que la operación pendiente no recorra nada: un :: en lugar de un ++, con el resultado parcial viajando hacia adentro en vez de armarse al volver.