Fibonacci & récursivité⚓︎
1. Fibonacci⚓︎
Écrire une fonction récursive permettant de calculer le n-ième élément de la suite de Fibonacci.
Exemples
2. La mémoïzation⚓︎
La récursivité permet d'avoir de belles fonctions, mais le temps d'exécution peut être très long !
Par exemple, pouvez-vous calculer le 50ème terme de la suite avec votre fonction ?
Normalement non ! Le problème vient du fait que des mêmes calculs sont effectués un très grand nombre de fois !
Pour le constater, vous pouvez rajouter un print(n)
au tout début de la fonction.
Lorsqu'on calcule fibo(5)
par exemple, on constate que :
fibo(4)
est appelé 1 fois,fibo(3)
est appelé 2 fois,fibo(2)
est appelé 3 fois,fibo(1)
est appelé 5 fois,fibo(0)
est appelé 3 fois.
La mémoïzation permet d'éviter cela, en mettant (en gros) un système de cache en place.
Mettez le en place, en vous aidant de ce site : https://python-course.eu/advanced-python/memoization-decorators.php.