Algoritmo de la Sucesión de Fibonacci en Python: Guía Completa y Ejemplos Prácticos

1. ¿Qué es la sucesión de Fibonacci?

La sucesión de Fibonacci es una serie numérica en la que cada término es la suma de los dos anteriores, comenzando típicamente con 0 y 1:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (para n > 1)

Esta secuencia aparece en la naturaleza (espirales de conchas, patrones de crecimiento de plantas) y en la informática (algoritmos de búsqueda, estructuras de datos, criptografía).

2. Implementaciones clásicas en Python

def fibonacci_recursive(n: int) -> int:
    """Calcula F(n) usando recursión directa.
    Complejidad temporal: O(2ⁿ) – exponencial.
    Complejidad espacial: O(n) – profundidad de pila.
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Ejemplo de uso
for i in range(10):
    print(f"F({i}) = {fibonacci_recursive(i)}")

def fibonacci_iterative(n: int) -> int:
    """Calcula F(n) de forma iterativa.
    Complejidad temporal: O(n).
    Complejidad espacial: O(1).
    """
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# Ejemplo de uso
for i in range(10):
    print(f"F({i}) = {fibonacci_iterative(i)}")

3. Optimización con memoización

La memoización almacena resultados intermedios para evitar cálculos redundantes. En Python podemos usar functools.lru_cache o implementar nuestro propio diccionario.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n: int) -> int:
    """Versión recursiva con memoización automática.
    Complejidad temporal: O(n).
    Complejidad espacial: O(n) – caché de resultados.
    """
    if n < 2:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

# Demo
print([fibonacci_memo(i) for i in range(15)])

Esta solución combina la claridad recursiva con la eficiencia lineal.

4. Generador de Fibonacci (Pythonic)

Los generadores permiten producir la secuencia bajo demanda, ideal para flujos infinitos o procesamiento en streaming.

def fibonacci_generator():
    """Generador infinito que produce números de Fibonacci.
    Uso típico: for i, val in enumerate(fibonacci_generator()):
                if i == n: break
    """
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Obtener los primeros 10 valores
gen = fibonacci_generator()
first_10 = [next(gen) for _ in range(10)]
print(first_10)

Los generadores son particularmente útiles en pipelines de datos y cuando se trabaja con asyncio o await combinados con async for.

5. Comparativa de rendimiento

Usaremos timeit para medir la ejecución de las distintas implementaciones con n = 35, un valor que ya muestra diferencias notables.

import timeit

setup = "from __main__ import fibonacci_recursive, fibonacci_iterative, fibonacci_memo"

print('Recursiva      :', timeit.timeit('fibonacci_recursive(35)', setup=setup, number=1))
print('Iterativa      :', timeit.timeit('fibonacci_iterative(35)', setup=setup, number=1000))
print('Memoizada      :', timeit.timeit('fibonacci_memo(35)', setup=setup, number=1000))

Como se puede observar, la versión iterativa es la más rápida y ligera, mientras que la memoizada ofrece un buen compromiso entre claridad y rendimiento.

6. Buenas prácticas y trucos avanzados

• Tip 1 – Usa int de Python sin límite: No hay riesgo de overflow, pero ten en cuenta que los números crecen exponencialmente y pueden consumir mucha memoria.
• Tip 2 – Evita la recursión profunda en CPython: El límite por defecto es 1000 llamadas; para n > 1000 considera la iteración o aumenta sys.setrecursionlimit() con cautela.
• Tip 3 – Vectoriza con NumPy (para grandes n): Cuando necesitas calcular cientos de miles de valores, la operación vectorizada en arrays es mucho más rápida.

import numpy as np

def fibonacci_numpy(k: int) -> np.ndarray:
    """Genera los primeros k números de Fibonacci usando matrices de transformación.
    Complejidad: O(log k) mediante exponenciación de matrices.
    """
    def mat_pow(mat, power):
        result = np.identity(2, dtype=object)
        while power:
            if power & 1:
                result = np.dot(result, mat)
            mat = np.dot(mat, mat)
            power //= 2
        return result

    base = np.array([[1, 1], [1, 0]], dtype=object)
    res = mat_pow(base, k)
    return np.array([res[1, 0], res[0, 0]])

print(fibonacci_numpy(10))  # → [55 89]

Esta técnica es útil en entornos de cálculo científico donde se combinan múltiples transformaciones lineales.

7. Casos de uso reales

1. Generación de claves criptográficas: Algunas variantes de algoritmos de firma utilizan números de Fibonacci para crear secuencias pseudo‑aleatorias.
2. Algoritmos de búsqueda en árboles balanceados: El árbol de Fibonacci (Fibonacci heap) mejora la complejidad de operaciones de disminución de clave.
3. Modelado de crecimiento biológico: Simulaciones de poblaciones de conejos u otras especies.
4. Arte generativo y música: La proporción áurea, derivada de la razón de números consecutivos de Fibonacci, inspira diseños visuales y composiciones musicales.

8. Depuración y troubleshooting

Si tu implementación devuelve resultados incorrectos, verifica los siguientes puntos:

• Los casos base (n==0 y n==1) están correctamente definidos.
• En la versión iterativa, no intercambies el orden de actualización (a, b = b, a + b).
• Al usar lru_cache, asegúrate de que la función no tenga efectos secundarios que dependan de variables externas.

Herramientas recomendadas: pdb para inspección paso a paso, pytest para pruebas unitarias y hypothesis para testing basado en propiedades.

9. Pruebas unitarias (pytest)

import pytest
from your_module import fibonacci_recursive, fibonacci_iterative, fibonacci_memo

@pytest.mark.parametrize("n,expected", [
    (0, 0), (1, 1), (2, 1), (3, 2), (5, 5), (10, 55), (15, 610)
])
def test_fibonacci_all(n, expected):
    assert fibonacci_recursive(n) == expected
    assert fibonacci_iterative(n) == expected
    assert fibonacci_memo(n) == expected

Ejecuta con pytest -q para validar que todas las versiones produzcan resultados consistentes.

10. Conclusiones

La sucesión de Fibonacci es más que un ejercicio académico; sus distintas implementaciones ilustran principios clave de la programación: recursión vs iteración, memoización, generación bajo demanda y optimización de complejidad. Elige la versión que mejor se adapte a tus requisitos de legibilidad, rendimiento y consumo de memoria.