Sucesión de Fibonacci
En este ejercicio implementarás la sucesión de Fibonacci, omnipresente en la naturaleza. La sucesión es la siguiente: "0, 1, 1, 2, 3, 5, 8…". Crearás una implementación recursiva de un algoritmo que genere la sucesión.
Los primeros números son 0 y 1, y el resto son la suma de los dos números anteriores.
Podemos definir esta sucesión recursivamente como: \(fib(n)=fib(n-1)+fib(n-2)\), with \(fib(0)=0\) y \(fib(1)=1\), being \(n\) la posición \(nth\) de la sucesión.
En el primer paso, programarás Fibonacci utilizando recursión. En el segundo paso, lo mejorarás utilizando programación dinámica, guardando las soluciones de los subproblemas en la variable cache.
Este ejercicio forma parte del curso
Estructuras de datos y algoritmos en Python
Ejercicio interactivo práctico
Pruebe este ejercicio completando este código de muestra.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))