La suite de Fibonacci est définie par
F0=0,
F1=1 et
Fn+2=Fn+1+Fn.
Écrire une version récursive naïve et montrer que sa complexité est exponentielle.Écrire une version avec mémoïsation et analyser sa complexité.Écrire une version itérative (bottom-up) en O(n) temps et O(1) espace.Écrire une version utilisant l'exponentiation rapide de matrices en O(logn).