Fibonacci debió ser todo un personaje en su época. Este hombre, cuyo nombre era Leonardo de Pisa ha pasado a la historia por su apodo, fibonacci (A su padre le llamabán "bonacci" -bonachón-, y el se quedó con fibonacci -el hijo de bonacci-).

Fibonacci fué en gran parte el responsable de que hoy utilicemos a nivel mundial la numeración de base 10 importada de las matemáticas árabes, junto con su grafía, las cifras de 0 a 10 que utilizamos normalmente. Además, introdujo el concepto del 0.

Para los estudiantes de programación es conocido porque uno de los ejercicios típicos de programación consiste en hallar un término de la Sucesión de Fibonacci.

Cuenta la leyenda que Fibonacci estaba observando cómo procreaban los conejos, y pensó que si un conejo hembra y uno macho podían procrear una pareja nueva cada mes a partir de su segundo mes... si cogíamos una pareja de conejos... ¿cuántos conejos tendríamos al cabo de unos cuantos meses?, por ejemplo, 12 meses.

Lee la explicación de Fibonacci en Gacetilla Matemática

El caso es que a partir de esta observación, la serie que tiene la forma que se indica a continuación se denomina "Sucesión de Fibonacci"

fib(1)=1
fib(2)=1
fib(n)=fib(n-1)+fib(n-2)    con n>=3
 

Así pues, la serie da estos valores...

1,1,3,5,8,13,21... etc.

En apariencia, puede parecer una tontería, sin embargo, es una sucesión simplemente apasionante, porque los términos de esa sucesión son a los que llegan a parar los sistemas naturales para un aprovechamiento máximo de la energía.

Por ejemplo, si observas un girasol o una piña, observaras que las pipas o los piñones forman espirales hacia la derecha y hacia la izquierda... pues bien, el número de espirales siempre forma parte de la sucesión de fibonacci.

Lo mismo ocurre con la estructura de todos los seres vivos siempre que es necesario aprovechar al máximo la energía.

También ocurre que la proporción entre dos terminos consecutivos de la sucesión de fibonacci termina convergiendo hacia un número irracional al que se le suele denominar phi, también conocido como "proporción aúrea" o "número de oro", que es otra proporción que podemos encontrar en la naturaleza una y otra vez, desde la estructura de los seres vivos, hasta los brazos de las grandes galaxias en espiral.

Pero volvamos a la sucesión, propiamente dicha.

Como habrás visto, la sucesión se define en términos recursivos a partir del tercero. Cada término es la suma de los dos anteriores.

Computacionalmente, también podría abordarse en términos recursivos, pero esto sí es realmente una tontería.

Programando con recursividad, dejamos el número de recursiones que podemos hacer en manos de la pila del sistema, que no sólo tiene una capacidad limitada, sino muy pequeña, y además, no tenemos control alguno sobre ésta. Si programamos la sucesión de fibonacci recursivamente, habrá algún valor de n que hará que se desborde la pila. Pero eso no es todo: lo peor es que no podemos conocer cuál es ese valor.

En programación no deberíamos utilizar nunca recursividad a menos que no quede otro remedio... y prácticamente siempre lo hay. A toda función recursiva se le puede aplicar una transformación y obtener una función iterativa equivalente. A veces, la versión iterativa de una función recursiva puede parecernos mucho más complicada, pero con la iteratividad podemos obtener un control total sobre la ejecución de la función, cosa que no tenemos con la recursividad.

El hecho de que en matemáticas se defina una función de forma recursiva no signifca que debamos programarlas de forma recursiva.

Este código en C# devuelve un término de la sucesión de Fibonacci.

static int FibonacciR(int n)
{
   if (n < 3)
      return 1;
   else
      return FibonacciR(n - 1) + FibonacciR(n - 2);
}
 

No obstante, tiene el problema que comentábamos antes. Algún valor de n provocará un desbordamiento de pila (Stack Overflow), ya que en cada llamada recursiva se almacena en la pila el contexto de ejecución de la función y los parámetros de la llamada, y a priori no conocemos el tamaño de la pila, pero sabemos que es relativamente pequeña, ya que su misión no es almacenar parámetros de llamadas recursivas, sino de llamadas no recursivas, en las cuales, el programador puede saber en todo momento cuántas llamadas hay en la pila.

Así pues, es necesario calcular los valores de la sucesión de forma iterativa. En el caso de la sucesión de Fibonacci es muy sencillo.

Basta con tener un bucle dentro del cual podamos disponer de dos variables: una para almacenar el valor del término de fibonacci de la iteración anterior, y otra para almacenar el de hace dos iteraciones.

Observa este código en C#

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