Exercice 11 - Suite de Fibonacci

1. Ecrire une fonction récursive unsigned long fibo(unsigned long l) calculant le $n$-ème nombre de fibonacci $F_n$ défini par récurrence de la sorte : $F_n = F_{n-1} + F_{n-2}$ avec $F_0 = 0$ et $F_1 = 1$.
2. Soit $u_n$ le nombre d'appels récursifs nécessaires pour calculer $F_n$. Prouvez par récurrence que $u_n \geq F_n$.
3. Exprimer $F_n$ en fonction de $n$ en résolvant la récurrence linéaire.
4. Déterminer la complexité de fibo en passant par une borne asymptotique inférieure.
5. On considère la fonction $\phi : (a, b) \mapsto (a + b, a)$. Prouvez que $\phi(F_{n-1}, F_{n-2}) =(F_{n}, F_{n-1})$.
6. On note $\phi^k$ la composition de $k$ fonctions $\phi$. Par exemple, $\phi^2 = \phi \circ \phi$ et $\phi^2(a, b) = \phi(\phi(a, b)) = \phi(a + b, a) = (2a + b, a + b)$. Par convention, $\phi^0$ est la fonction identité, notée $id$. Prouver par récurrence que $(F_{n+1}, F_{n}) = \phi^n(F_1, F_0))$.
7. Implémentez $\phi$ avec le sous-programme void phi(unsigned long* l1, unsigned long* l2), notez que les deux variables l1 et l2 sont passées en paramètre par référence.
8. Ecrivez le corps du sous-programme void applyF(void (*f)(unsigned long*, unsigned long*), int n, unsigned long* l1, unsigned long* l2), applyF applique n fois la fonction f, en utilisant comme paramètre lors du premier appel les variables pointées par l1 et l2.
9. Utilisez applyF et phi pour coder unsigned long fastFibo(unsigned long l)
10. Majorer la complexité de applyF lorsqu'on lui passe le sous-programme phi en paramètre, prouver ce résultat par récurrence.
11. Quelle est la complexité de fastFibo ? Porte-t-elle bien son nom ?