Sequenza di Fibonacci
In questo esercizio implementerai la sequenza di Fibonacci, onnipresente in natura. La sequenza è questa: "0, 1, 1, 2, 3, 5, 8…". Creerai un'implementazione ricorsiva di un algoritmo che genera la sequenza.
I primi numeri sono 0 e 1, e i successivi sono la somma dei due numeri precedenti.
Possiamo definire questa sequenza in modo ricorsivo come: \(fib(n)=fib(n-1)+fib(n-2)\), con \(fib(0)=0\) e \(fib(1)=1\), dove \(n\) è la \(n\)-esima posizione nella sequenza.
Nel primo step, scriverai il codice di Fibonacci usando la ricorsione. Nel secondo step, lo migliorerai usando la programmazione dinamica, salvando le soluzioni dei sottoproblemi nella variabile cache.
Questo esercizio fa parte del corso
Strutture dati e algoritmi in Python
Esercizio pratico interattivo
Prova a risolvere questo esercizio completando il codice di esempio.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))