raiz5 = (5)**0.5
φ = (1 + raiz5)/2
ψ = (1 - raiz5)/2

calculados = {}

def fibo_rec(n):
    if n <= 1:
        return n
    if n in calculados:
        return calculados[n]
    resultado = fibo_rec(n-1) + fibo_rec(n-2)
    calculados[n] = resultado
    return resultado

def fibo_fechado(n):
    return (φ**n - ψ**n)/raiz5

for n in range(100):
    print(f"{n=}\n    {fibo_rec(n)=}\n{fibo_fechado(n)=}\n")