Aller au contenu

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
Python Console Session
>>> fibo(0)
1
>>> fibo(1)
1
>>> fibo(2)
2
>>> fibo(3)
3
>>> fibo(4)
5
>>> fibo(5)
8
>>> fibo(10)
89

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.