Secuencia Fibonacci

El problema

Crea una función fibonacci(n) que devuelva el n-ésimo número de la secuencia de Fibonacci (empezando desde 0).

La secuencia es: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Cada número es la suma de los dos anteriores: F(n) = F(n-1) + F(n-2)

Ejemplos

Código inicial

def fibonacci(n):
    # Tu código aquí
    pass


print(fibonacci(0))   # 0
print(fibonacci(1))   # 1
print(fibonacci(10))  # 55
print(fibonacci(20))  # 6765

El problema de la recursión ingenua

La solución más obvia — y la más lenta — es la recursión directa:

def fibonacci_lento(n):
    if n <= 1:
        return n
    return fibonacci_lento(n - 1) + fibonacci_lento(n - 2)

Parece simple, pero fibonacci_lento(40) tarda varios segundos porque recalcula el mismo valor miles de veces. Para fibonacci_lento(50) esperarías minutos.

¿Por qué? Porque fibonacci_lento(5) llama a fibonacci_lento(4) y fibonacci_lento(3). Y fibonacci_lento(4) también llama a fibonacci_lento(3). Ese árbol de llamadas crece exponencialmente: O(2ⁿ).

def fibonacci(n):
  if n <= 1:
      return n
  a, b = 0, 1
  for _ in range(2, n + 1):
      a, b = b, a + b
  return b


print(fibonacci(0))   # 0
print(fibonacci(1))   # 1
print(fibonacci(10))  # 55
print(fibonacci(20))  # 6765
print(fibonacci(50))  # 12586269025 (¡instantáneo!)

Memoización con @lru_cache

Si prefieres la elegancia de la recursión, Python tiene una solución en una línea:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 1:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

print(fibonacci_memo(100))  # 354224848179261915075 (instantáneo)

@lru_cache almacena en caché los resultados ya calculados. La primera llamada a fibonacci_memo(10) calcula todo; la segunda devuelve el resultado guardado en memoria.

Generador: la forma pythónica para secuencias

Si necesitas todos los números hasta el n-ésimo, usa un generador:

def fib_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Primeros 10 números de Fibonacci
fib = fib_generator()
primeros_10 = [next(fib) for _ in range(10)]
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Los generadores son perfectos para secuencias infinitas: generan un valor cada vez sin almacenar toda la secuencia en memoria.

Comparativa de rendimiento

import time

# Recursiva ingenua: exponencial O(2^n)
# fibonacci_lento(40) → ~40 segundos

# Iterativa: lineal O(n), memoria O(1)
# fibonacci(1000) → microsegundos

# Con lru_cache: O(n) primera vez, O(1) si ya calculado
# fibonacci_memo(1000) → microsegundos

Próximos pasos

• Implementa secuencia_fibonacci(n) que devuelva una lista con los primeros n números
• Comprueba si un número dado pertenece a la secuencia de Fibonacci
• Investiga la fórmula de Binet: permite calcular F(n) en O(1) usando matemáticas