Suite de Fibonacci
Dans cet exercice, vous allez implémenter la suite de Fibonacci, omniprésente dans la nature. La suite ressemble à ceci : « 0, 1, 1, 2, 3, 5, 8… ». Vous allez créer une implémentation récursive d'un algorithme qui génère cette suite.
Les deux premiers nombres sont 0 et 1, et chaque nombre suivant est la somme des deux précédents.
On peut définir cette suite de façon récursive ainsi : \(fib(n)=fib(n-1)+fib(n-2)\), avec \(fib(0)=0\) et \(fib(1)=1\), où \(n\) est la \(n^e\) position dans la suite.
À la première étape, vous coderez Fibonacci en utilisant la récursion. À la deuxième étape, vous l'améliorerez au moyen de la programmation dynamique, en enregistrant les solutions des sous-problèmes dans la variable cache.
Cette activité fait partie du cours
Structures de données et algorithmes en Python
Exercice interactif pratique
Essayez cet exercice en complétant ce code d’exemple.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))