Más Funciones Recursivas en Erlang parte 2

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

Si representamos ésta de manera similar a la versión normal, obtenemos:

tail_reverse([1,2,3,4]) = tail_reverse([2,3,4], [1])

                        = tail_reverse([3,4], [2,1])

                        = tail_reverse([4], [3,2,1])

                        = tail_reverse([], [4,3,2,1])

                        = [4,3,2,1]   

Lo que muestra que la cantidad de elementos visitados para revertir nuestra lista ahora es lineal: no solo evitamos hacer crecer la pila, ¡sino que también hacemos nuestras operaciones de una manera mucho más eficiente!