reversa: la concatenación que queda pendiente en cada marcoEl 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.
++ ha recorrido:
0reversa(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.
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.