Terminal ou non

(* A *) let rec longueur = function [] -> 0 | _ :: r -> 1 + longueur r
(* B *) let rec cherche x = function
          | [] -> false
          | y :: r -> if x = y then true else cherche x r
(* C *) let rec somme acc = function [] -> acc | x :: r -> somme (acc + x) r
(* D *) let rec deux_puiss n = if n = 0 then 1 else 2 * deux_puiss (n - 1)

• A : non terminal. Après le retour de longueur r, il reste à ajouter $1$ : l'activation doit survivre à son appel. Profondeur $\Theta (n)$.
• B : terminal. Dans la branche else, le résultat de cherche x r est rendu tel quel. Le if n'y change rien : le résultat de la branche choisie est le résultat de la fonction. Espace $O(1)$.
• C : terminal. C'est la forme à accumulateur : tout le calcul se fait avant l'appel, dans l'argument. Espace $O(1)$.
• D : non terminal. Il reste la multiplication par $2$. Profondeur $\Theta (n)$.

Le critère opératoire : demandez-vous ce qu'il resterait à faire si l'appel rendait sa valeur à l'instant. Si la réponse est « rien, je la rends », l'appel est terminal.

Attention à un cas que l'œil rate. Un appel enfermé dans un try ... with n'est jamais terminal, même quand il en a toute l'apparence : il reste à faire quelque chose après lui, à savoir démonter le gestionnaire d'exception. Le dernier exercice de cette série le mesure.