Explorateur d'arbres de récursivité

Choisissez une définition récursive. Fixez n. Regardez combien d'appels sont effectués, et combien résolvent un problème déjà traité ailleurs.

Exemple résolu — Explorateur d'arbres de récursivité

Appels effectués	25
Sous-problèmes distincts	7
Appels par sous-problème	3,6
Imbrication maximale	5
Cas de base atteints	13
Étapes de combinaison	12

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Explorateur d'arbres de récursivité

Un arbre de récursivité correspond à un nœud par appel : la racine est l'appel que vous avez lancé, et les enfants d'un nœud sont les appels qu'il effectue. On en tire trois nombres. Le nombre de nœuds représente le temps d'exécution en unités d'« un appel ». La hauteur indique la profondeur atteinte par la pile. Enfin, le nombre de nœuds différents correspond au temps d'exécution que vous obtiendriez si chaque réponse était mémorisée dès son premier calcul.

Comment lire ce que vous voyez

La page s'ouvre sur fib(6). Son arbre est suffisamment petit pour être dessiné en entier : 25 nœuds, dont 7 marquent la première apparition de leur sous-problème. C'est pourquoi la carte des sous-problèmes distincts indique 7 et celle des appels par sous-problème 3,6. L'imbrication maximale est de 5, le long de fib(6) → fib(5) → … → fib(1). Sur les 25 appels, 13 atteignent un cas de base et les 12 autres additionnent chacun deux valeurs de retour.

Ne tient plus quand: Le nombre d'appels par sous-problème est une promesse concernant la mémoïsation. Hanoï est l'exemple même de sa rupture. Pour n = 20, Hanoï signale 21 sous-problèmes distincts pour 2 097 151 appels, soit 99 864,3 appels par sous-problème. C'est 95,8 fois le chiffre de Fibonacci pour le même n. Le mémoïser ne permet aucune économie exploitable. La réponse à hanoi(20) est une liste de 1 048 575 déplacements, et renvoyer une liste mémorisée coûte le même prix que de la générer. Un tableau de mémoïsation est rentable lorsque la réponse est courte et que l'arbre est grand. La réponse de Fibonacci tient en un seul entier. Celle de Hanoï est l'arbre lui-même, entièrement retranscrit.

Fibonacci, calculé en comptant des un 🖖

Fixez n à 20. L'arbre contient 21 891 appels. Parmi eux, 10 946 atteignent un cas de base, et les 10 945 autres sont des additions. Seul fib(1) renvoie 1, fib(0) renvoyant 0. Sur toutes ces feuilles, 6 765 portent donc un un et 4 181 ne portent rien. F(20) vaut 6 765, ce qui correspond très exactement au nombre de un. Chaque valeur renvoyée par la récursivité est une somme de certains d'entre eux. Ce principe ne change pas avec n : la carte des cas de base indique toujours F(n+1), et la quantité de un parmi eux est toujours égale à F(n).

Deux arbres de 21 891 appels, mais un seul se répète 🖖

Le calcul naïf de fib(20) et le tri fusion de 10 946 éléments font très exactement le même nombre d'appels : 21 891, répartis en 10 946 cas de base et 10 945 étapes de combinaison. Trois des six cartes affichent des résultats identiques, et les deux définitions créent deux branches à chaque nœud interne. Ce n'est donc pas la ramification qui les sépare. La carte des sous-problèmes distincts est formelle : 21 contre 21 891. Un tableau de mémoïsation réduit l'arbre de Fibonacci à 21 unités de travail, mais laisse celui du tri fusion à 21 891. Les moitiés du tri fusion sont des tranches différentes d'un seul et même tableau. Une réponse mise en cache pour « une suite de 5 473 éléments » correspondrait inévitablement aux 5 473 mauvais éléments.

Un seul 1 soustrait sépare φⁿ de 2ⁿ 🖖

Hanoï et Fibonacci font tous deux deux appels récursifs et atteignent presque la même profondeur, 20 contre 19. Pour n = 20, Hanoï effectue 2 097 151 appels. Fibonacci en fait 21 891, soit 95,8 fois moins. La seule différence dans le code se situe au niveau du deuxième argument récursif : Hanoï s'appelle deux fois sur n−1, Fibonacci sur n−1 puis sur n−2. Cette simple soustraction fait chuter la base de l'exponentielle de 2 à φ = 1,618. Et l'écart continue de se creuser. À n = 30, nous avons 2 147 483 647 appels contre 2 692 537, soit un facteur de 798.

Problèmes entièrement résolus

Formule explicite du nombre d'appels quand fib(10) naïf effectue 177 appels 6 étapes
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 = 2 L - 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, 2 F_{1} - 1 = 2 F_{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 + (2 F_{n} - 1) + (2 F_{n - 1} - 1) = 2 F_{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 φ ^{n + 1}}{5} = 1 0^{8} ⟹ φ^{n + 1} = \frac{1 0 ^{8} 5}{2} = 1.1180 \times 1 0^{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 ( 1.1180 \times 1 0 ^{8} )}{ln φ} = \frac{18.5323}{0.4812} = 38.51$
Réponse

n = 37. L'outil confirme les deux valeurs voisines : 78 176 337 appels pour n = 37, et 126 491 971 pour n = 38. Au-delà, chaque augmentation de 1,44 de n double le travail, car ln 2 / ln φ = 1,44. Pendant ce temps, la carte des sous-problèmes distincts affiche 38 pour n = 37. Soixante-dix-huit millions d'appels pour répondre à trente-huit questions : voilà, en une seule phrase, tout l'argument de la programmation dynamique.
Trois branches qui croissent moins vite que deux 6 étapes
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.

Ouvrez ce problème dans l'outil
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.
  
  $fib : x^{2} = x + 1 \Rightarrow φ = 1.6180340; hanoi : C (n) = 1 + 2 C (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.839286 8^{20} = 196, 331 against 128, 287 ⟹ A = 0.6534; 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$
Réponse

Hanoï croît plus vite, 2 contre 1,8393, et la troisième branche ne coûte aux marches rien qu'elles ne puissent payer. Le facteur de branchement est une borne supérieure du taux de croissance, et il n'est atteint que lorsque chaque enfant est plus petit d'un seul pas. Les marches dépensent deux de leurs trois appels sur des arguments diminués de 2 et de 3, et ces sous-arbres sont assez bon marché pour ne jamais totaliser la branche qu'elles semblaient avoir gagnée.

La recette est ce qu'il faut garder, car elle fonctionne sur une définition que personne n'a résolue pour vous. Comptez les enfants, notez de combien chacun abaisse l'argument, écrivez x à la plus grande baisse comme somme des x aux baisses restantes, et prenez la plus grande racine réelle. Une mise en garde l'accompagne : c'est un fait sur l'arbre naïf, et l'arbre naïf n'est pas ce que quiconque écrirait. La carte des sous-problèmes distincts affiche 21 à n = 20 pour les marches et 21 pour Hanoï : une mémoïsation supprime donc l'exposant entièrement, et le taux de croissance cesse de compter.

$x^{k} = j \sum m_{j} x^{k - j} (m_{j} children at n - j, k = max j) : 1.8393 < 2$

Parcours

Compter le travail, pas les secondes

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.