Récursion terminale : ce que coûte l'attente

let rec somme_naive = function [] -> 0 | x :: r -> x + somme_naive r

let somme_acc l =
  let rec aux acc = function [] -> acc | x :: r -> aux (acc + x) r in
  aux 0 l

La différence tient à une addition. Dans somme_naive, l'appel récursif n'est pas la dernière chose faite : au retour, il reste à calculer x + .... Chaque niveau doit donc survivre à son appel, avec sa valeur de x : la pile grandit avec la longueur de la liste, soit $\Theta (n)$ en espace.

Dans somme_acc, l'appel aux (acc + x) r est la dernière expression évaluée ; il n'y a rien à faire au retour. On dit l'appel terminal, et le compilateur le transforme en saut : l'espace de pile reste $\Theta (1)$. Les deux fonctions sont en $\Theta (n)$ en temps.

La mesure. Sur OCaml 5.4, la pile grandit dynamiquement, et il faut aller loin pour la remplir :

let rec profond n = if n = 0 then 0 else 1 + profond (n - 1)

profond    20 000 000 : ok
profond    40 000 000 : Stack_overflow

Le seuil se déplace d'une machine à l'autre, et l'on peut l'abaisser à volonté par la variable d'environnement OCAMLRUNPARAM. Avec OCAMLRUNPARAM=l=100000, la mesure devient nette :

n =  100 000 : somme_naive leve Stack_overflow, somme_acc = 5000050000
n =  500 000 : somme_naive leve Stack_overflow, somme_acc = 125000250000

somme_acc traverse tout, quelle que soit la limite.