Fibonacci-reeks
In deze oefening implementeer je de Fibonacci-reeks, die overal in de natuur voorkomt. De reeks ziet er zo uit: "0, 1, 1, 2, 3, 5, 8…". Je maakt een recursieve implementatie van een algoritme dat de reeks genereert.
De eerste getallen zijn 0 en 1, en de rest is de som van de twee voorgaande getallen.
We kunnen deze reeks recursief definiëren als: \(fib(n)=fib(n-1)+fib(n-2)\), met \(fib(0)=0\) en \(fib(1)=1\), waarbij \(n\) de \(n\)-de positie in de reeks is.
In de eerste stap codeer je Fibonacci met recursie. In de tweede stap verbeter je dit met dynamic programming, waarbij je de oplossingen van de deelproblemen bewaart in de variabele cache.
Deze oefening maakt deel uit van de cursus
Datastructuren en algoritmen in Python
Interactieve oefening met praktijkervaring
Probeer deze oefening door deze voorbeeldcode aan te vullen.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))