Un appel qui semble terminal et ne l'est pas

(* A *) let compte n =
          let rec aux acc k = if k = 0 then acc else aux (acc + k) (k - 1) in
          aux 0 n

(* B *) let compte n =
          let rec aux acc k =
            if k = 0 then acc
            else (try aux (acc + k) (k - 1) with Division_by_zero -> 0)
          in aux 0 n

(* C *) let compte n =
          let rec aux acc k = if k = 0 then acc else aux (acc + k) (k - 1) in
          try aux 0 n with Division_by_zero -> 0

C'est B qui déborde. Mesuré, avec l'interprète ocaml :

n = 10^7 : A -> 50000005000000    B -> 50000005000000    C -> 50000005000000
n = 10^8 : A -> 5000000050000000  B -> Stack_overflow    C -> 5000000050000000

Pourquoi. Le try ... with installe un gestionnaire d'exception avant l'appel, et il faut le démonter après. Il reste donc quelque chose à faire au retour : l'appel n'est pas en position terminale, le bloc d'activation ne peut pas être réutilisé, et l'espace redevient $\Theta (n)$.

Le piège est redoutable parce que B a l'air d'une récursion terminale : accumulateur, appel en dernière position, rien après lui à l'œil nu. Ce qui ne se voit pas, c'est le travail que le try laisse à faire.

La parade est C**** : installer le gestionnaire une seule fois, autour de la récursion et non dedans. Le comportement en cas d'exception est le même, et l'appel redevient terminal.

Le seuil, mesuré par dichotomie sur la profondeur : la version B déborde à partir de $14913060$ appels, tandis que A et C passent $2\times 10^8$ sans broncher. La différence entre « aucun espace » et « un bloc par appel » n'est donc pas une subtilité de langage : elle décide si le programme rend un résultat ou meurt.