Probleme – Le débordement de pile, mesuré en OCaml et en C

1. En OCaml. On instrumente deux fonctions de même effet, l'une non terminale, l'autre à accumulateur, puis on cherche le seuil par dichotomie :

let rec descend n = if n = 0 then 0 else 1 + descend (n-1)   (* NON terminal *)
let rec monte acc n = if n = 0 then acc else monte (acc+1) (n-1)  (* terminal *)

non terminal   : plus grande profondeur sans erreur      33 554 384
                 (soit 2^25 mots, la taille de pile par defaut du bytecode)
terminal       : aucun debordement a 2 x 10^8 appels
terminal + try : deborde des 14 913 060 -- le try annule l'optimisation

La récursion terminale n'occupe pas la pile : c'est mesurable, et c'est ce qui autorise le style à accumulateur d'OCaml sans arrière-pensée.

2. En C. Même programme, deux jeux d'options :

long somme_t(long n, long acc) {          /* appel TERMINAL */
    if (n == 0) { return acc; }
    return somme_t(n - 1, acc + n);
}
long somme_nt(long n) {                   /* appel NON terminal */
    if (n == 0) { return 0; }
    return n + somme_nt(n - 1);
}

gcc -O0 : les DEUX meurent en violation de segment vers 174 000 appels
          (pile de 8 Mio / 174 000 = environ 48 octets par bloc d'activation)
gcc -O2 : les DEUX vont a 10^7 sans broncher

Le résultat est plus fort que prévu, et il faut le dire tel quel. À -O2, le compilateur transforme en boucle non seulement la fonction terminale, mais aussi la fonction non terminale : il reconnaît que l'addition est associative et fabrique lui-même un accumulateur. Autrement dit, le même code source, compilé deux fois, meurt ou survit selon une option de la ligne de commande. Rien dans la norme du langage ne promet l'une ou l'autre issue.

C'est exactement l'avertissement du cours, ici chiffré : en C, la profondeur de récursion est une caractéristique de la compilation, pas du programme.

3. La discipline.

• En OCaml, la récursion terminale est fiable : le compilateur la garantit, et l'on peut y engager des profondeurs arbitraires. La récursion non terminale reste bornée par la pile — on la réserve aux profondeurs logarithmiques ou aux structures dont la hauteur est petite.
• En C, on n'engage jamais une profondeur qu'on ne sait pas majorer. Une récursion en $O(\log n)$ (dichotomie, arbre équilibré) est sans danger ; une récursion en $O(n)$ sur une donnée fournie par l'utilisateur est une faille — c'est ainsi qu'on fait tomber un analyseur syntaxique avec une expression très imbriquée.
• Dans les deux langages, la bonne question n'est pas « boucle ou récursion ? » mais « quelle est la profondeur maximale, et sais-je la majorer ? ». Si la réponse est $O(\log n)$, la récursion est le meilleur choix parce qu'elle est plus lisible et se prouve mieux. Si elle est $O(n)$ et $n$ non borné, il faut un accumulateur, une boucle, ou une pile explicite — cette dernière ramenant le problème du chapitre chap:sequentielles au tas, où l'on sait mesurer et agrandir.