Probleme – Ce que coûte un appel, mesuré

1. La mesure. L'astuce tient en une variable locale : deux appels emboîtés placent leur locale dans deux blocs consécutifs, et la différence de leurs adresses est la taille du bloc.

static long profondeur = 0;
static char* base = NULL;

void descendre(void) {
    char marque;                              /* une locale, n'importe laquelle */
    profondeur = profondeur + 1;
    if (base == NULL) { base = &marque; }     /* on retient la premiere */
    fprintf(stderr, "%ld %ld\n", profondeur, (long) (base - &marque));
    descendre();
}

On écrit sur stderr et non sur stdout : c'est le seul flux non tamponné, donc le seul dont les dernières lignes survivent à une mort brutale. Sur stdout, on perdrait précisément l'information qu'on cherche — c'est la mesure de l'exercice « Deux sorties, deux destins » mise à profit.

Mesures : les premières lignes sont 1 0, 2 48, 3 96. Un bloc d'activation fait $48$ octets, et l'écart est parfaitement régulier.

2. La profondeur. Le programme meurt avec le code $139$ (SIGSEGV) après $174228$ appels. Confrontation :

$$174228\times 48=8362944\text{contre}8176\text{kio}=8372224\text{octets}.$$

L'écart, $9280$ octets, est la place occupée par le bloc de main, l'amorçage de la bibliothèque standard, et le bloc que fprintf doit encore pouvoir se réserver au dernier appel réussi. Le compte tombe juste à $0,1\%$ près : la pile est bien un tableau de taille fixe, et la récursion en consomme les cases une par une.

Une remarque de méthode. Cette mesure ne se transporte pas. Le même procédé appliqué, sur la même machine, à une fonction de trois paramètres portant un tableau local de $1000$ octets donne un bloc de $1072$ octets et une profondeur maximale de $7801$ : $22,3$ fois plus gros, $22,3$ fois moins profond — et $174228/7801=22,3$ également, ce qui confirme que le produit reste la taille de la pile. Ce qui se transporte, c'est donc le procédé : deux adresses de locales, une soustraction.

3. Une récursion de profondeur $10^6$. Trois réponses, de la moins bonne à la meilleure.

Augmenter la pile (ulimit -s unlimited, ou l'option d'édition de liens correspondante) : cela repousse le mur sans le supprimer, et rend le programme dépendant de la configuration de la machine qui l'exécute. On ne livre pas un programme ainsi.

Rendre la récursion terminale. Si l'appel récursif est la dernière opération de la fonction, le compilateur peut réutiliser le bloc courant au lieu d'en empiler un nouveau. C'est ce que fait systématiquement OCaml (chapitre chap:langage-ocaml) ; en C, gcc -O2 le fait souvent, mais ce n'est pas une garantie du langage : le même code compilé sans optimisation déborde. On ne fonde pas une correction sur une optimisation facultative.

Gérer une pile explicite. On remplace la pile d'appels par un tableau ou une liste que l'on empile soi-même. Le coût en mémoire est le même, mais il est sur le tas : la seule limite devient la mémoire de la machine, et l'on peut la vérifier, la borner, et rendre une erreur au lieu de mourir. C'est la technique qui permet, au chapitre chap:arbres, de parcourir un arbre de $10^7$ nœuds dégénéré en peigne — et l'on y mesurera que la version récursive, elle, s'arrête.

La règle qui résume les trois. Une profondeur de récursion bornée par une constante ou logarithmique en la taille de la donnée est saine. Une profondeur linéaire est un défaut de conception qu'il faut savoir reconnaître à l'écriture, et non découvrir en production.