Șirul Fibonacci
În acest exercițiu, vei implementa șirul Fibonacci, care apare frecvent în natură. Șirul arată astfel: "0, 1, 1, 2, 3, 5, 8…". Vei crea o implementare recursivă a unui algoritm care generează acest șir.
Primele două numere sunt 0 și 1, iar restul reprezintă suma celor două numere precedente.
Putem defini acest șir recursiv astfel: \(fib(n)=fib(n-1)+fib(n-2)\), cu \(fib(0)=0\) și \(fib(1)=1\), unde \(n\) este poziția \(n\) în șir.
În primul pas, vei implementa Fibonacci folosind recursivitatea. În al doilea pas, vei îmbunătăți soluția prin programare dinamică, salvând rezultatele subproblemelor în variabila cache.
Acest exercițiu face parte din cursul
Structuri de date și algoritmi în Python
Exercițiu interactiv practic
Încearcă acest exercițiu completând acest cod de exemplu.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))