EL DRAMA DE FIBONACCI

Si la implementación recursiva de la función factorial es, aparte de ineficiente, peligrosa por la posibilidad de provocar un desbordamiento de pila, hay otros problemas en los que la cantidad de llamadas que se producen aumentan muchísimo los riesgos y la ineficiencia. Un ejemplo sencillo de esto es la Sucesión de Fibonacci.

Nuevamente, la definición en terminos recursivos de la sucesión de Fibonacci es muy elegante y sencilla de entender:

-El primer y segundo término de la sucesión (n=1 y n=2) es 1
-Del tercero en adelante (n>2), es la suma de los dos términos anteriores.

En un lenguaje un poquito más matemático...

fib(1)=1
fib(2)=1
fib(n)=fib(n-1)+fib(n-2)     cuando n>2
 

Precioso... lo digo en serio. Es el colmo de la elegancia. Definimos dos casos base (n=1 y n=2), y el resto se definen en función de los dos inmediatamente anteriores.

Por ejemplo, el término tercero (n=3) es la suma de los dos casos base, es decir, 2. El cuarto es la suma del tercero (2) y el segundo (1), es decir, 3. El quinto es la suma del cuarto (3) y del tercero (2), es decir, 5... y así sucesivamente.

Sin embargo, computacionalmente hablado, implementar la función de Fibonacci en estos términos recursivos no es tan elegante, aunque pudiera parecerlo.

        static int fib(int n) {
            int resultado;
                if (n==1)
                    resultado=1;
                else if(n==2)
                    resultado=1;
                else
                    resultado=fib(n-1)+fib(n-2);
                return resultado;
            }
 

En esta función, si la invocamos, por ejemplo con n=6, debemos tener en cuenta que al no ser un caso base, se vuelve a invocar recursivamente DOS veces, con n=5, y con n=4. A su vez, cada una de esta, necesita DOS llamadas más, y cada una esas DOS más... y así hasta llegar a los casos base, que no necesitan una nueva llamada, y son los que cortan esta cascada de llamadas recursivas.

Si represento estas llamadas recursivas gráficamente, el resultado es una estructura arborescente binaria, con una profundidad que depende del n inicial.

En esta representación, en cada círculo se representa el valor de n para una invocación de la función, empezando con n=6. Para calcular fib(6), es necesario calcular fib(5) y fib(4)... y para calcular fib(4) es necesario calcular fib(3) y fib(2).... y así sucesivamente. La recursividad se corta con fib(2) o fib(1), que son los casos base. ¡Imagina el tamaño del gráfico para calcular fib(25)!... tendría unos 150000 nodos.

La cantidad de llamadas que son necesarias para calcular fib(6), es de 15 nada menos. En un instante dado, la cantidad de llamadas máxima que hay es de 5 (la profundidad del arbol).

Pero hay otra cosa que asombra más todavía... fíjate que fib(4) se calcula dos veces, y que fib(3) se calcula tres veces. Realmente sólo es necesario hacerlo una vez. ¿Para qué tantas?... bueno... por la propia implementación recursiva de la función. Calcular fib(100) con este algoritmo haría una y otra vez lo mismo tantas veces que tardaría una barbaridad en finalizar.

Por supuesto, en el caso de la sucesión de Fibonacci también es sencillo obtener una versión iterativa.

Basta percatarse de que para calcular fib(6) podemos empezar por calcular fib(1) y fib(2), que son muy fáciles por ser los casos base, y anotarlo, por ejemplo, en un par de variables.

a=1   //fib(1)
b=1   //fib(2)

Sabiendo esto, ¿Puedo calcular fib(3) con el contenido de a y b?... Por supuesto... voy a almacenarlo en una variable llamada c.

a=1   //fib(1)
b=1   //fib(2)
c=2   //fib(3)

Para calcular fib(4) necesito conocer fib(3) y fib(2)... Vamos a aplicar el ingenio. Ya no necesito fib(1), contenido en a, así que voy a "desplazar" el contenido de las variables... voy a almacenar fib(2) en a, y fib(3) en b, dejando libre c. En ese c, voy a almacenar fib(4), simplemente sumando a y b

a=1   //fib(2)
b=2   //fib(3)
c=3   //fib(4)

Repito la operación para fib(5)

a=2   //fib(3)
b=3   //fib(4)
c=5   //fib(5)

Otra vez para fib(6)

a=3   //fib(4)
b=5   //fib(5)
c=8   //fib(6)

Anda... ya he llegado. Tengo almacenado en c el valor de fib(6)... Cuatro iteraciones y tres variables... y en ningún momento calculo más de una vez ningún termino de la sucesión.

Esta función implementa esta solución. (Tomada del artículo Sucesión de Fibonacci)

static int Fibonacci(int n)
{
    if (n < 3) //los dos primeros terminos son 1
        return 1;
    else // a partir del tercero
    {
        int a = 1;
        int b = 1;
        int contador = 2;
        int c;
        do
        {
            contador++; //término que calcula esta iteración
            c = a + b; //calcular término
            //preparo las variables para la próxima vuelta
            a = b;
            b = c;
        } while (n != contador);
        return c;
     } //fin else
}
 

Con esta implementación, calcular fib(100) toma apenas un instante, mientras que con la implementación recursiva toma una cantidad de tiempo que escapa de lo razonable en un entorno productivo.