Los números de Fibonacci

Introducción

La sucesión de los números de Fibonacci¹ aparece a menudo en las clases de programación, ya que puede ser utilizada para enseñar dos temas muy importantes: ciclos y recursión.

Lo que ahora conocemos como la sucesión² de Fibonacci ya había sido estudiada desde tiempos remotos por matemáticos de la India. Sin embargo, fue hasta el año 1202 que el matemático italiano Leonardo de Pisa, también conocido como Fibonacci, describió esta sucesión al mundo occidental en su libro titulado Liber Abaci (El libro del cálculo). La sucesión de Fibonacci tiene aplicaciones en matemáticas y ciencia de la computación. Aparece también con frecuencia en la naturaleza, por ejemplo en la disposición de las hojas en el tallo de una planta o el cono de un pino.

Leonardo de Pisa,
alias Fibonacci

La sucesión de Fibonacci fue explicada por Leonardo de Pisa de una manera un tanto pintoresca. Supongamos que tenemos una pareja (un macho y una hembra) de conejos recién nacidos. Estos conejos alcanzan su madurez sexual a los dos meses de edad y a partir de ese momento, en cada mes sucesivo, pueden reproducirse dando a luz a una nueva pareja (también un macho y una hembra). Suponiendo, así mismo, que los conejos nunca se mueren y que no tienen problemas con el incesto entre hermanos, podemos calcular el número de parejas de conejos que se van acumulando a través de los meses:

La sucesión de Fibonacci a partir de una pareja de conejos.

En los meses 1 y 2 solo hay una pareja de conejos. Para el mes 3 la pareja ya tuvo a su primer par de hijos, por tanto hay dos parejas en total. Para el mes 4, la pareja original vuelve a tener otro par de hijos, pero la pareja que nació en el mes 3 todavía no puede tener hijos. Esto quiere decir que hay un total de tres parejas en el mes 4. Para el mes 5, la pareja original vuelve a tener un nuevo par, y la pareja que nació en el mes 3 ya tiene también su primer par. El mes 5 termina con cinco parejas a partir de las tres que ya había más las dos que nacieron ese mes.

Podemos observar que para calcular el número total de parejas de conejos en un cierto mes n basta con sumar las parejas que ya existen (el total del mes anterior a n) más las nuevas parejas que nacerán durante ese mes (el total de parejas que había dos meses antes de n, ya que todas esas parejas están sexualmente maduras para el mes n).

A partir de lo que hemos planteado podemos definir a la sucesión de Fibonacci como una sucesión infinita de números enteros cuyos primeros dos elementos son 0 y 1 (aunque la figura de arriba no lo muestra, está implícito que en el mes 0 hay cero parejas de conejos), y todos los elementos posteriores son la suma de los dos anteriores:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

En términos matemáticos, tenemos la siguiente relación de recurrencia: $$ \textrm{fib}(n) = \left\{\begin{matrix} 0 & \textrm{si} \; n = 0 \\ 1 & \textrm{si} \; n = 1\\ \textrm{fib}(n - 1) + \textrm{fib}(n - 2) & \textrm{si} \; n > 1 \end{matrix}\right. $$

Implementación recursiva

La ecuación de la sección anterior puede traducirse directamente a Python (simplificando un poco las condiciones) para obtener una función recursiva:

# Fibonacci version recursiva
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

Se puede probar la función desde el shell de Python:

>>> fib(0)
0
>>> fib(1)
1
>>> fib(5)
5
>>> [fib(i) for i in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

Aunque elegante, la definición anterior es extremadamente ineficiente. Por ejemplo, la siguiente figura muestra todas las operaciones que se requieren para calcular el elemento de la sucesión cuando n=5. Los rectángulos representan llamadas recursivas a la función fib, mientras que los círculos representan los resultados devueltos del caso base.

En este caso, para calcular fib(5), se requiere primero calcular fib(4) y fib(3). Pero para calcular fib(4) se requiere calcular también fib(3) (además de fib(2)). Aquí es donde se puede ver el origen de la ineficiencia: varias operaciones se realizan múltiples veces. Del árbol de la figura anterior podemos ver que:

• fib(5) se realiza en total 1 vez.
• fib(4) se realiza en total 1 vez.
• fib(3) se realiza en total 2 veces.
• fib(2) se realiza en total 3 veces.
• fib(1) se realiza en total 5 veces.

Observando el total de veces que se realiza cada llamada a fib para un cierto valor, no debe resultar muy sorprendente notar que la sucesión de Fibonacci también aparece ahí.

Si el número que se desea obtener de la sucesión es relativamente grande
(n > 30), el tiempo que tarda en terminar la función puede ser considerable. El lector puede intentar calcular fib(35) para poderse dar una idea.

Memoización

Para corregir el problema mencionado anteriormente podemos recurrir a una técnica de optimización conocida como memoización (no confundir con memorización), la cual consiste en evitar que las llamadas a una función repitan los cálculos asociados a argumentos previamente procesados. La manera de implementar esta técnica es bastante sencilla usando un diccionario inicialmente vacío. Cuando una función f es invocada con un argumento x, se revisa si x existe como llave en el diccionario. En caso afirmativo, la función termina inmediatamente devolviendo el valor del diccionario asociado a x. En caso negativo, se calcula y devuelve de manera normal el resultado de f(x), pero antes de terminar la función se guarda dicho resultado en el diccionario asociándolo a la llave x. Con esto logramos que para cada valor de x solo se calcule f(x) a lo mucho una vez.

El beneficio de la técnica de memoización es lograr una mejora en el tiempo de ejecución de una función. El principal inconveniente es que requiere utilizar más memoria (para guardar todos los resultados que se vayan calculando).

Vale la pena memoizar una función f siempre y cuando se cumplen las tres siguientes condiciones:

• f es referencialmente transparente. Esto significa, para fines de nuestra discusión, que f siempre devuelve exactamente el mismo resultado si se invoca con el mismo argumento de entrada.
• El tiempo de acceso al diccionario debe ser perceptiblemente menor al tiempo de ejecución de f.
• f debe ser invocada en nuestro programa de manera bastante frecuente con los mismos argumentos.

Nuestra implementación recursiva de la sucesión de Fibonacci cumple con las tres condiciones.

Este es el código de la función fib de la sección anterior modificado para incluir memoización tal como se describió arriba:

# Fibonacci version recursiva con memoizacion
cache = {0: 0, 1: 1}
def fib(n):
    if n not in cache:
        cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

Como se puede observar, se añadió la variable global cache, a la cual se le asigna un diccionario con las llaves 0 y 1, y cuyos valores asociados son también 0 y 1 respectivamente (los primeros dos valores de la sucesión). Con ello se puede eliminar el código que de manera explícita checa los casos base de la definición recursiva. La variable cache tiene que ser global³ dado que deseamos que el diccionario preserve sus valores entre dos o más invocaciones de fib.

El lector ahora puede verificar que fib devuelve un resultado prácticamente de manera instantánea:

>>> fib(35)
9227465
>>> fib(100)
354224848179261915075

Implementación iterativa

Tal como vimos desde la sección de introducción, para poder calcular el elemento n de la sucesión de Fibonacci solo se requieren los dos elementos anteriores. A partir de los dos elementos iniciales podemos determinar cualquier elemento posterior en la sucesión usando un simple ciclo. En cada iteración del ciclo se deben actualizar un par de variables con el fin de que éstas siempre contengan los valores de los dos últimos elementos de la sucesión calculados hasta el momento.

El código quedaría así:

# Fibonacci version iterativa
def fib(n):
    a = 1
    b = 0
    for i in range(n):
        a, b = b, a + b
    return b

La función define dos variables locales: a y b. La variable b representa el último elemento de la sucesión calculado hasta el momento, mientras que a representa el penúltimo. Si b se inicializa con 0, ¿con qué valor se debe inicializar a dado que debe ser un elemento anterior al 0 en la sucesión? La respuesta es 1, ya que en la siguiente iteración el nuevo valor de b debe ser 1, y debe ser a su vez el resultado de sumar los valores previos de a y b (1 y 0, respectivamente).

El ciclo for se repite n veces gracias a la función range(). El cuerpo del ciclo se encarga de actualizar las variables a y b con el fin de tener un nuevo último y un nuevo penúltimo elemento al final de cada iteración. Por ejemplo, al inicio de la sexta iteración a=3 y b=5. Al termino de esa iteración a debe tener el valor original de b, y b debe tener la suma de los valores originales de a y b. Es decir, a=5 y b=8. Esto se logra en Python con la instrucción

a, b = b, a + b

la cual se conoce como una “asignación paralela”. Ésta consiste en asignar de manera simultánea las variables del lado izquierdo del símbolo de asignación con los valores que están del lado derecho.

De forma un poco más general:

a, b, c, d = 1, 2, 3, 4

es equivalente a:

a = 1
b = 2
c = 3
d = 4

La ventaja de este tipo de instrucción es que podemos usar las mismas variables en ambos lados de la asignación sin preocuparnos por el orden en que serán actualizadas y sin tener que introducir variables temporales.

En nuestro caso, si no tuviéramos forma de hacer una asignación paralela, la instrucción del cuerpo del ciclo tendría que ser dividida en tres instrucciones además de requerir una variable temporal t:

t = b
b = a + b
a = t

Si no se introduce la variable temporal t la variable a terminaría con el mismo nuevo valor de b y no con el valor anterior de b.

Finalmente, una vez que el ciclo termina, la variable b contiene el elemento deseado y por tanto se devuelve usando la instrucción return.

Podemos probar nuestro código para valores chicos y grandes de n:

>>> fib(1)
1
>>> fib(100)
354224848179261915075
>>> [fib(i) for i in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

Nuestra solución iterativa es computacionalmente mucho más eficiente que la primera versión recursiva, a tal grado que ni siquiera hace falta recurrir a la técnica de memoización descrita anteriormente para obtener un buen desempeño.

---

Notas:

¹ Mucha de la información aquí presentada fue tomada del artículo Fibonacci number de Wikipedia.

² Frecuentemente a la “sucesión de Fibonacci” se le ha llamado erróneamente “serie de Fibonacci”. “Sucesiones” y “series” pueden parecer la misma cosa, pero en realidad una serie es la suma de una sucesión. Por ejemplo, dada la sucesión: {1, 2, 3, 4}, la serie correspondiente a ésta sería: 1+2+3+4=10.

³ El principal problema de que la variable cache sea global es que se puede leer y modificar, de manera intencional o accidental, desde cualquier otra parte del programa. Por eso es que procuramos desalentar en nuestros alumnos el uso de variables globales. Pero entonces, ¿qué alternativas tenemos? Una opción consiste en definir una clase en la que se utilice una variable de instancia para encapsular al diccionario que se requiere en el proceso de memoización. Otra opción es usar cerraduras léxicas (lexical closures en inglés) para definir un decorador que memoice funciones de manera genérica. Lamentablemente, ambas opciones hacen que este ejercicio sea mucho más complejo, así que, por simplicidad y por el momento, mejor nos quedamos con una variable global.