Combien d'appels coûte le chevauchement

let rec fib n = if n < 2 then n else fib (n-1) + fib (n-2)

Démonstration, par récurrence forte sur $n$.

Base. $A(0)=A(1)=1$ (un seul appel, celui du sommet). Et $2F(1)-1=2\cdot 1-1=1$, $2F(2)-1=2\cdot 1-1=1$. La formule tient.

Hérédité. Pour $n\ge 2$, l'appel au sommet en engendre deux : $A(n)=1+A(n-1)+A(n-2)$. Par hypothèse,

$$A(n)=1+(2F(n)-1)+(2F(n-1)-1)=2(F(n)+F(n-1))-1=2F(n+1)-1.$$

Vérification, mesurée en instrumentant la fonction :

n :        4     6     8    10    12     20      25       30
appels :   9    25    67   177   465  21891  242785  2692537
2F(n+1)-1: 9    25    67   177   465  21891  242785  2692537

Ce que la formule dit. Comme $F(n)\sim {\phi }^n/\sqrt{5}$ avec $\phi =(1+\sqrt{5})/2$, le nombre d'appels est $\Theta ({\phi }^n)$ : exponentiel. Pour $n=30$, deux millions et demi d'appels pour calculer un nombre à sept chiffres.

Et la conclusion à ne pas tirer. Ce n'est pas « la récursivité est chère ». Le nombre de valeurs distinctes en jeu est $n+1$ ; c'est le chevauchement qui est cher, c'est-à-dire le fait de recalculer $F(k)$ autant de fois qu'il apparaît dans l'arbre. Retenir les valeurs déjà calculées ramène le coût à $\Theta (n)$ sans changer une ligne de la décomposition : c'est toute la programmation dynamique du chapitre chap:dynamique.