Explorateur d'arbres de récursivité

L'outil indique que fib(10) naïf effectue 177 appels et que fib(11) en fait 287. Trouvez la forme explicite du nombre d'appels, prouvez-la, puis déterminez jusqu'où va l'algorithme de Fibonacci naïf en une seconde sur une machine capable de traiter 10⁸ appels par seconde.

1. Ajoutez 1 à chaque compte : 178 et 288. Ces deux nombres sont pairs, et leurs moitiés sont 89 et 144, qui correspondent à F₁₁ et F₁₂. La conjecture est donc C(n) = 2F(n+1) − 1, avec F(1) = F(2) = 1.

   $$C(10)=177,C(11)=287⟹\frac{178}{2}=89=F_{11},\frac{288}{2}=144=F_{12}$$

2. L'arbre explique l'origine de ce doublement. Chaque nœud interne effectue exactement deux appels et chaque feuille n'en fait aucun. Un arbre avec L feuilles possède donc L − 1 nœuds internes, soit un total de 2L − 1 nœuds. L'outil signale 89 cas de base pour n = 10, et 2 × 89 − 1 = 177.

   $$N=2L-1⟹2\times 89-1=177$$

3. Les cas de base d'abord. fib(0) et fib(1) retournent leur valeur sans faire d'appel récursif. Nous avons donc C(0) = C(1) = 1, et les deux expressions 2F(1) − 1 et 2F(2) − 1 sont égales à 1.

   $$C(0)=C(1)=1,2F_1-1=2F_2-1=1$$

4. Passez maintenant à la récurrence. Supposons la formule vraie pour n − 1 et n − 2. L'appel en n correspond à un nœud plus ses deux sous-arbres, et les deux nombres de Fibonacci sous-jacents fusionnent selon la définition même de la suite. Fixer n = 11 donne 2 × 144 − 1 = 287. C'est exactement ce qu'affiche l'outil.

   $$C(n)=1+C(n-1)+C(n-2)=1+(2F_n-1)+(2F_{n-1}-1)=2F_{n+1}-1$$

5. Laissez l'arbre de côté. La formule de Binet donne F(m) = (φ^m − ψ^m)/√5 avec φ = 1,6180 et |ψ| < 1. F(m) correspond donc à φ^m/√5 arrondi à l'entier le plus proche, et C(n) ≈ 2φⁿ⁺¹/√5. Une seconde à 10⁸ appels par seconde permet de réaliser 10⁸ appels. Cela fixe φⁿ⁺¹ à 1,1180 × 10⁸.

   $$C(n)\approx \frac{2{\phi }^{n+1}}{\sqrt{5}}=10^8⟹{\phi }^{n+1}=\frac{10^8\sqrt{5}}{2}=1.1180\times 10^8$$

6. Passez aux logarithmes. ln(1,1180 × 10⁸) = 18,5323 et ln φ = 0,4812, donc n + 1 = 38,51 et n = 37,5. Arrondissez à l'entier inférieur, car un appel fractionnaire ne se termine jamais.

   $$n+1=\frac{\ln \left(1.1180\times 10^8\right)}{\ln \phi }=\frac{18.5323}{0.4812}=38.51$$

L'escalier à trois pas s'appelle trois fois à chaque nœud ; les tours de Hanoï s'appellent deux fois. Chargez Marches à 20, 3 branches, cherchez lequel des deux arbres croît le plus vite, et décidez ce que vaut le facteur de branchement comme repère.

1. Lisez la récurrence sur la définition plutôt que sur l'image. Un appel pour le nœud lui-même, puis trois autres en n − 1, n − 2 et n − 3, et tout ce qui est à 2 ou en dessous renvoie sans récursion.

   $$C(n)=1+C(n-1)+C(n-2)+C(n-3),C(0)=C(1)=C(2)=1$$

2. Supposez que le nombre croît géométriquement, C(n) ≈ A xⁿ, et substituez. Divisez le tout par x à la puissance n − 3 : le 1 de tête reste en arrière comme bruit d'ordre inférieur, et il ne demeure qu'une cubique. Sa seule racine réelle vaut 1,8392868, la constante tribonacci.

   $$C(n)\sim A{x}^n⟹x^3=x^2+x+1⟹x=1.8392868$$

3. La même recette sur les deux autres définitions. Fibonacci s'appelle en n − 1 et n − 2, donc x² = x + 1 et la racine vaut φ = 1,6180340. Hanoï s'appelle deux fois en n − 1, donc x = 2 et il n'y a rien à résoudre.

   $$\text{fib}:x^2=x+1\Rightarrow \phi =1.6180340;\text{hanoi}:C(n)=1+2C(n-1)\Rightarrow x=2$$

4. Vérifiez-le plutôt que d'y croire. Mettez n à 29, lisez la carte des appels effectués, mettez n à 30, relisez, divisez. Les marches donnent 1,83929, Fibonacci 1,61803, Hanoï exactement 2. Cinq décimales pour les trois.

   $$\frac{C(30)}{C(29)}:\frac{56,843,233}{30,905,041}=1.83929,\frac{2,692,537}{1,664,079}=1.61803,\frac{2^{31}-1}{2^{30}-1}=2.00000$$

5. Ce que la racine ne vous donne pas, c'est le nombre. 1,8393²⁰ vaut 196 331 alors que la carte affiche 128 287 : il y a donc un facteur 0,65 devant. Les appels de Hanoï valent exactement 2ⁿ⁺¹ − 1, soit un facteur 2. Les cas de base fixent cette constante et la récurrence fixe la racine, et seule la racine décide qui l'emporte à la fin.

   $$1.8393^{20}=196,331\text{against}128,287⟹A=0.6534;\text{hanoi}:C(n)=2^{n+1}-1,A=2$$

6. Cette fin arrive vite ici. À n = 20, Hanoï fait 16,3 fois plus d'appels que les marches, et à n = 30 il en fait 37,8 fois plus. Le rapport double tous les 8,3 pas, puisque ln 2 divisé par ln(2 ÷ 1,8393) vaut 8,27.

   $$\frac{2^{21}-1}{128,287}=16.3,\frac{2^{31}-1}{56,843,233}=37.8,\frac{\ln 2}{\ln (2/1.8393)}=8.27$$