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.
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:
(Actualizado 28/05/2015)
