Sequência de Fibonacci
Neste exercício, você implementará a sequência de Fibonacci, que é onipresente na natureza. A sequência é a seguinte: "0, 1, 1, 2, 3, 5, 8…". Você criará uma implementação recursiva de um algoritmo que gera a sequência.
Os primeiros números são 0 e 1, e os demais são a soma dos dois números anteriores.
Podemos definir essa sequência recursivamente como: \(fib(n)=fib(n-1)+fib(n-2)\), with \(fib(0)=0\) e \(fib(1)=1\), being \(n\) a posição \(nth\) na sequência.
Na primeira etapa, você codificará o Fibonacci usando recursão. Na segunda etapa, você o aprimorará usando a programação dinâmica, salvando as soluções dos subproblemas na variável cache.
Este exercício faz parte do curso
Estruturas de dados e algoritmos em Python
Exercício interativo prático
Experimente este exercício preenchendo este código de exemplo.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))