Exercice 34 - Expérimentation avec la suite de Fibonacci

Ecrivez une fonction récursive retournant le $n$-ème nombre de Fibonacci (noté $F_n$) en utilisant la relation de récurrence suivante :

• $F_0 = 0$
• $F_1 = 1$
• $F_n = F_{n-1} + F_{n-2}$

Que remarquez-vous lorsque l'on calcule des valeurs de la suite de Fibonacci avec de grandes valeurs de $n$ (control-C pour interrompre l'exécution d'un programme :-) ? On considère, pour remédier à ce petit problème la fonction $\phi$ définie comme suit

• $\phi(a, b, 0) = b$
• $\phi(a, b, n) = \phi(a + b, a, n-1)$

Prouvez par récurrence sur $n$ que $F_{n + k} = \phi(F_{k + 1}, F_k, n)$, puis que $F_n = \phi(1, 0, n)$. Utilisez cette relation pour modifier la fonction calculant le $n$-ème nombre de Fibonacci. Tester l'algorithme d'Euclide étendu avec des couples $(F_n, F_{n-1})$ (prenez de grandes valeurs de $n$).