Problème — Le coût caché de Fibonacci

Problème — Le coût caché de Fibonacci.

On reprend la fonction fibonacci naïve du cours ($F_0=0$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$). On note $A_n$ le nombre total d'appels déclenchés par fibonacci(n), appel initial compris.

• Calculer $A_0$, $A_1$, $A_2$, $A_3$ et établir une relation de récurrence pour $A_n$.
• Vérifier sur les premières valeurs que $A_n=2F_{n+1}-1$, puis le démontrer par récurrence.
• En déduire le nombre d'appels pour $n=30$, sachant que $F_{31}=1346269$.
• Écrire une version itérative en $O(n)$, et expliquer pourquoi elle permet aussi de calculer $F_{5000}$, contrairement à toute version récursive descendant de $n$ à $0$ un par un.