Curiosidades de la Programación: Más sobre Recursividad Terminal (Tail Recursion)

Introducción

En el artículo anterior sobre Recursividad Terminal incluí la siguiente conclusión:

Algo muy interesante de la Recursividad Terminal es que no es necesario almacenar las llamadas recursivas en la pila de ejecución, lo que evita su desbordamiento. Además, en teoría, podría permitir realizar una implementación recursiva en un lenguaje que no tenga soporte para ello.

¿Te has preguntado si es posible utilizar Recursividad Terminal si la función requiere varias invocaciones recursivas?

A continuación intentaré demostrar empíricamente la citada conclusión a la vez que demostraré que sí es posible usar Recursividad Terminal aunque se necesiten varias invocaciones recursivas.

La sucesión de Fibonacci

La sucesión de Fibonacci es una sucesión matemática infinita de números naturales en la que cada valor se calcula como la suma de los dos valores anteriores. Unas fuentes la definen a partir de 0 y 1 mientras que otras lo hacen a partir de 1 y 2. Me voy a quedar con la que empieza en 0.

N	00	01	02	03	04	05	06	07	08	09	10
Valor	0	1	1	2	3	5	8	13	21	34	55

Se define recursivamente con dos invocaciones a sí misma:

*fibonacci(N)*	si N es 0 entonces 0	//Caso base 1.
	si N es 1 entonces 1	//Caso base 2.
	en otro caso, *fibonacci*(N-1) + *fibonacci*(N-2)	//Doble llamada recursiva.

Es un caso muy conocido que servirá para ilustrar el uso de Recursividad Terminal con varias invocaciones recursivas.

Implementación recursiva natural

Empecemos por la implementación recursiva natural. En este caso he utilizado C++, más adelante explicaré por qué.

double fibonacci_rec(int n) {
    double f;
    
    if (n <= 0) {
        f= 0;
    }
    else if (n == 1) {
        f= 1;
    }
    else {
//        f= fibonacci_rec(n - 1) + fibonacci_rec(n - 2);
        double one= fibonacci_rec(n - 1);
        double two= fibonacci_rec(n - 2);
        f= one + two;
    }
    
    return f;
}

He utilizado un estilo de programación en el que he tratado de desglosar todas las operaciones de alto nivel, para que sea más fácil comparar las diferentes implementaciones.

He llamado one al resultado de la invocación con N-1 y two al resultado de la invocación con N-2.

He utilizado double simplemente porque la función crece muy rápido y usando un int el resultado se desborda fácilmente.

Implementación recursiva terminal

Recuérdese que la Recursividad Terminal se basa en la idea de calcular todo lo necesario antes de realizar las llamadas recursivas, pasando ese cálculo intermedio a la invocación mediante argumentos.

En este caso, en teoría se necesitarían 2 llamadas recursivas, por lo que hay que realizar 2 cálculos intermedios y pasar 2 argumentos extra.

double fibonacci_tail_inner(int n, double one, double two) {
    double f;

    if (n <= 0) {
        f= 0;
    }
    else if (n == 1) {
        f= one;
    }
    else {
//        f= fibonacci_tail_inner(n - 1, one + two, one);
        double tmp= one + two;
        two= one;
        one= tmp;
        n= n - 1;

        f= fibonacci_tail_inner(n, one, two);
    }

    return f;
}

double fibonacci_tail(int n) {
    return fibonacci_tail_inner(n, 1, 0);
}

En este caso, he llamado one al acumulador de la invocación N-1 y two al acumulador de la invocación N-2. Los cálculos que hay que realizar en cada llamada son:

el one que se pasa a la llamada recursiva es la suma del one y el two actuales.
el two que se pasa a la llamada recursiva es el one actual.

Sólo ha quedado una única llamada recursiva. Hay que tener en cuenta que esto no es un detalle nimio, ya que esta implementación es muchísimo más rápida por tener un coste lineal (N), mientras que la implementación recursiva natural tiene un coste exponencial (2^N-1).

Implementación sin pila de ejecución: goto

Sí sí, has leído bien, he utilizado la operacion goto para demostrar que es posible hacer una implementación recursiva terminal sin ir apilando las invocaciones. Dicha característica, la posibilidad de usar variables globales y la disponibilidad de GCC son la razones de que haya utilizado C++ .

Discusiones "goto sí goto no" aparte, la operación goto no deja de ser una herramienta que en este caso me ha venido genial para realizar una implementación recursiva sin llamadas a subrutinas.

static int g_n;
static double g_one;
static double g_two;
static double g_f;
#define pseudocall_fibonacci_goto_inner() goto l_start

double fibonacci_goto_inner() {
l_start:
    if (g_n <= 0) {
        g_f= 0;
    }
    else if (g_n == 1) {
        g_f= g_one;
    }
    else {
        double tmp= g_one + g_two;
        g_two= g_one;
        g_one= tmp;
        g_n= g_n - 1;

        pseudocall_fibonacci_goto_inner(); //goto l_start;
    }

    return g_f;
}

double fibonacci_goto(int n) {
    g_one= 1;
    g_two= 0;
    g_n= n;
    g_f= -1;

    return fibonacci_goto_inner();
}

Para evitar suspicacias, he utilizado variables globales (g_n, g_one, g_two y g_f), dejando solamente la variable local tmp necesaria para poder calcular los valores de g_one y g_two para la "siguiente llamada recursiva". Al ser variables globales, sólo existen una única vez en memoria: no se instancian en la pila de ejecución cuando se necesitan, sino que están en el bloque de memoria estática del programa.

Al comienzo de la función fibonacci_goto_inner está la etiqueta l_start, que es el punto al que se salta cada vez que se desea simular una llamada recursiva, es decir, la "llamada recursiva" consiste saltar al comienzo de la función. Por estética, se puede "ocultar" la sentencia goto con una macro.

No hay ninguna llamada a subrutina, por lo que no se apila nada en la pila de ejecución: las únicas posiciones de memoria ocupadas son las de las variables globales y la variable local tmp.

Se puede comprobar visualmente que esta solución es prácticamente idéntica a la versión anterior, salvo por el uso de variables globales y la simulación de la llamada recursiva.

Optimización

Gracias a Avelino Herrera Morales sé que el GCC soporta Tail Call Optimization utilizando la opción -foptimize-sibling-calls, incluida en las opciones -O2 y -O3 (aparentemente sola no funciona, necesita acompañarse de -O1). Aparte de este comentario, utilizando el comando objdump me enseñó que el código generado con dicho flag no genera ninguna instrucción de llamada a subrutina (call o similar).

Probablemente, la solución que aplique el compilador sea muy similar a la que yo he expuesto aquí (pero con variables locales claro), es decir, simplemente sustituir la llamada recursiva por un simple salto al comienzo de la función sin apilar ni desapilar nada en la pila de ejecución.

Pruebas

En este enlace puedes ver un pequeño programa que incluye todas las implementaciones de la función Fibonacci de este artículo y una versión interativa.

C++ Fibonacci Recursion Test

Variando la variable MAX de la función main se puede comprobar fácilmente que la implementación recursiva natural es lentísima, volviéndose desesperante a partir de 50.

Con valores grandes de MAX (en mi caso, un valor cercano a 33333) se puede provocar que se desborde la pila en la implementación recursiva terminal sin optimizar sin que se desborde la pila en la implementación recursiva terminal con goto. Si se activa la optimización, se puede comprobar que no se desborda en ninguno de esos dos casos. En teoría, la versión recursiva natural también se desbordaría, pero en la práctica es tan lenta que no se puede comprobar (hay que desactivar esa parte del código para hacer pruebas de fuerza bruta).

Conclusión

Tal y como dije en la introducción ha quedado demostrado:

que en un escenario donde no se dispone de la gestión de la pila de ejecución (al escribir en ensamblador a mano por ejemplo), es posible simular una implementación recursiva empleando un esquema de Recursividad Terminal.
que la Recursividad Terminal se puede utilizar con funciones que requieran varias llamadas recursivas.

Destaco que la implementación Recursiva Terminal, si está optimizada, evita los problemas de desbordamiento de pila (Stack Overflow) de la solución Recursiva Natural. De hecho, la solución implementada con goto demuestra que no se necesita ni la pila.

Enlaces

Enlaces de interés relacionados con este artículo:

¿Qué es la sucesión de Fibonacci?
http://curiosidades.batanga.com/4461/que-es-la-sucesion-de-fibonacci
Sucesión de Fibonacci - Wikipedia
http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci
Recursividad Terminal (Tail Recursion) en este mismo blog
http://programacion-curiosidad.blogspot.com.es/2015/04/recursividad-terminal-tail-recursion.html
http://stackoverflow.com/questions/18582333/is-this-tail-recursion
http://runnable.com/U44bs7vG_3wKYXUm/tail-recursive-fibonacci-c%2B%2B-for-recursion
https://gist.github.com/enigmaticape/4013070
http://stackoverflow.com/questions/22111252/tail-recursion-fibonacc
https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

(Actualizado 28/05/2015)

Curiosidades de la Programación

jueves, 28 de mayo de 2015

Más sobre Recursividad Terminal (Tail Recursion)