La recursividad "infinita" de Lisp

La posibilidad de aprovechar toda la potencia de la recursividad es uno de los puntos fuertes (hay tantos) de los lenguajes funcionales y aunque voy a hablar de Lisp, ya que es el lenguaje funcional que mejor conozco, lo que voy a decir es aplicable a Scheme, Haskell, etc.

Para la explicación usaré el típico ejemplo de calcular el factorial de un número. El código en Lisp para realizar el cálculo (que nadie se asuste con los paréntesis) sería:

(defun factorial (n)
   (cond ((= n 1) 1)
         (t (* n (factorial (- n 1))))))

La misma función escrita en C sería la siguiente:

int factorial (int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial (n - 1);
}

Sin embargo, esta forma de calcular el factorial de un número suele encontrarse únicamente en libros de programación para explicar el mecanismo de la recursividad. Cualquier programador sabe que cada vez que llamamos a una función el sistema operativo almacena en la pila el estado actual del programa para recuperarlo después cuando vuelva de la llamada a la función, con lo que si queremos calcular el factorial de un número muy grande corremos el riesgo de sufrir un desbordamiento de pila con efectos un tanto desagradables para nuestro programa.

Por esa razón los programadores de C calcularían el factorial de la siguiente forma:

int factorial (int n) {
    int r = 1, n2 = n;

    while (n2 > 1) {
        r = r * n2;
        n2--;
    }

    return r;
}

Ahora evitamos el problema del desbordamiento de pila y el programa, al ser iterativo, es mucho más rápido, aunque el código no resulta tan fácil de leer ni tan lógico como la versión recursiva.

Pero, en contra de lo que podría esperarse, el código en Lisp funciona igual de rápido que el código en C y además, podemos calcular factoriales de números inmensos sin que la pila se inmute. ¿Cómo es posible? Es posible gracias al trabajo del intérprete de Lisp y a una técnica conocida como Tail Recursion (recursividad por cola).

Lo que hace el intérprete de Lisp es sustituir nuestra función por esta otra:

(defun factorial (n &optional (r 1))
    (cond ((= n 1) r)
          (t (factorial (- n 1) (* r n)))))

Si nos fijamos bien veremos que la nueva función no necesita volver sobre sus pasos para calcular el factorial, sino que va calculando el resultado antes de la llamada recursiva. Esto permite que no sea necesario usar la pila, ya que no hace falta regresar a través de todas las llamadas, sino que la última es la que devolverá el resultado directamente.

Si bien es cierto que muchos compiladores de lenguajes imperativos como C tienen en cuenta este tipo de funciones y las tratan como funciones iterativas, los intérpretes y compiladores de lenguajes funcionales lo hacen de forma implícita, lo que permite un código mucho más claro y legible.