Le peigne et la pile

Les mesures, en OCaml 5.4.1 :

Pourquoi le peigne, et pas un autre arbre. La profondeur de récursion de taille est la hauteur de l'arbre, pas sa taille. Sur un arbre équilibré de $10^7$ nœuds, la hauteur vaut $23$ : aucun risque. Sur un peigne de $10^7$ nœuds, elle vaut $10^7-1$. C'est donc l'encadrement du cours, $h\le n-1$, qui se paye ici en octets de pile, et il se paye au moment où l'arbre a déjà dégénéré.

La version qui ne déborde pas. On remplace la pile d'appels par une pile que l'on gère soi-même, et qui vit sur le tas :

(* Nombre de noeuds de a, sans recursion sur la hauteur.
   La pile explicite vit sur le TAS : sa taille n'est plus bornee par
   ulimit -s mais par la memoire de la machine. Complexite : Theta(n). *)
let taille_iter a =
  let pile = ref [a] and n = ref 0 in
  let continuer = ref true in
  while !continuer do
    match !pile with
    | [] -> continuer := false
    | Vide :: r -> pile := r
    | Noeud (g, _, d) :: r -> incr n; pile := g :: d :: r
  done;
  !n

Invariant : !n est le nombre de nœuds déjà comptés, et !pile contient exactement les sous-arbres qui restent à visiter, deux à deux disjoints. Variant : le nombre total de nœuds contenus dans !pile, qui décroît strictement à chaque tour.

Le tableau des trois langages, mesuré.

Trois conclusions, dans l'ordre d'importance.

Un. L'écart entre C et OCaml — un facteur $60$ au moins — n'est pas une propriété des langages, mais de leur mise en œuvre : la pile d'un processus C est un bloc de taille fixe, celle d'OCaml 5 s'agrandit à la demande. Un programme ne doit dépendre ni de l'un ni de l'autre.

Deux. Stack_overflow est une exception rattrapable en OCaml, là où le débordement en C est un SIGSEGV qui tue le processus (chapitre chap:memoire). C'est une différence de confort, pas de correction : dans les deux cas, le calcul n'a pas eu lieu.

Trois, et c'est le seul qui serve. Une profondeur de récursion égale à la hauteur est saine tant que l'arbre est équilibré. Tout le chapitre suivant existe pour garantir cette hypothèse, et cet exercice mesure ce qu'il en coûte de ne pas la garantir.