Hay una propiedad interesante que podemos "descubrir" cuando comparamos funciones recursivas y recursivas de cola escribiendo una función inversa/1, que invertirá una lista de términos. Para tal función, el caso base es una lista vacía, para la cual no tenemos nada que revertir. Podemos simplemente devolver una lista vacía cuando eso suceda. Cualquier otra posibilidad debería intentar converger al caso base llamándose a sí mismo, como con duplicado/2. Nuestra función iterará a través de la lista haciendo coincidir el patrón [H|T] y luego poniendo H después del resto de la lista:
reverse([]) -> [];
reverse([H|T]) -> reverse(T)++[H].
En listas largas, esto será una verdadera pesadilla: no solo acumularemos todas nuestras operaciones de agregados, sino que también necesitaremos recorrer toda la lista para cada uno de estos agregados hasta el último. Para los lectores visuales, los numerosos controles se pueden representar como:
reverse([1,2,3,4]) = [4]++[3]++[2]++[1]
↑ ↵
= [4,3]++[2]++[1]
↑ ↑ ↵
= [4,3,2]++[1]
↑ ↑ ↑ ↵
= [4,3,2,1]
Aquí es donde la recursividad de cola viene al rescate. Debido a que usaremos un acumulador y le agregaremos un nuevo encabezado cada vez, nuestra lista se invertirá automáticamente. Primero veamos la implementación:
tail_reverse(L) -> tail_reverse(L,[]).
tail_reverse([],Acc) -> Acc;
tail_reverse([H|T],Acc) -> tail_reverse(T, [H|Acc]).