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 créerez une implémentation récursive d'un algorithme qui génère cette suite.
Les deux premiers nombres sont 0 et 1, et les suivants sont la somme des deux nombres précédents.
On peut définir cette suite de manière récursive comme suit : \(fib(n)=fib(n-1)+fib(n-2)\), avec \(fib(0)=0\) et \(fib(1)=1\), où \(n\) est la position \(n\)-ième dans la suite.
Dans la première étape, vous coderez Fibonacci à l'aide de la récursion. Dans la seconde, vous l'améliorerez en utilisant la programmation dynamique, en enregistrant les solutions des sous-problèmes dans la variable cache.
Cet exercice fait partie du cours
<cours>Structures de données et algorithmes en Python</cours>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))