Fibonacci-sekvensen
I den här övningen implementerar du Fibonacci-sekvensen, som förekommer överallt i naturen. Sekvensen ser ut så här: "0, 1, 1, 2, 3, 5, 8…". Du skapar en rekursiv implementation av en algoritm som genererar sekvensen.
De två första talen är 0 och 1, och resten är summan av de två föregående talen.
Vi kan definiera sekvensen rekursivt som: \(fib(n)=fib(n-1)+fib(n-2)\), där \(fib(0)=0\) och \(fib(1)=1\), och \(n\) är positionen i sekvensen.
I det första steget implementerar du Fibonacci med rekursion. I det andra steget förbättrar du lösningen med hjälp av dynamisk programmering – du sparar resultaten från delproblemen i variabeln cache.
Den här övningen är en del av kursen
Datastrukturer och algoritmer i Python
Interaktiv övning med praktiskt arbete
Testa den här övningen genom att slutföra den här exempelkoden.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))