Fibonacci

Escribe una función fib(n) que retorne el número n de la secuencia de Fibonacci.

La secuencia de Fibonacci se define como:

• fib(0) = 0
• fib(1) = 1
• Para n >= 2: fib(n) = fib(n-1) + fib(n-2)

Debes resolver el problema usando recursión. Si puedes, implementa también una solución optimizada usando memoization.

Ejemplo:

fib(0) -> 0
fib(1) -> 1
fib(5) -> 5
fib(8) -> 21

Restricciones:

• 0 ≤ n ≤ 50
• Se espera que la solución tenga buena eficiencia para valores grandes como n = 40 o n = 50