Séquence de Fibonacci
Dans cet exercice, vous mettrez en œuvre la séquence de Fibonacci, qui est omniprésente dans la nature. La séquence se présente comme suit : "0, 1, 1, 2, 3, 5, 8…". Vous allez créer une implémentation récursive d'un algorithme qui génère la séquence.
Les premiers nombres sont 0 et 1, et les autres sont la somme des deux nombres précédents.
Nous pouvons définir cette séquence de manière récursive comme suit : \(fib(n)=fib(n-1)+fib(n-2)\), with \(fib(0)=0\) et \(fib(1)=1\), being \(n\) la position \(nth\) dans la séquence.
Dans la première étape, vous allez coder Fibonacci en utilisant la récursivité. Dans un deuxième temps, 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))