informatique (MP2I/MPI) · Chapitre 5 · Application directe du cours
Terminal ou non
Récursivité · niveau 2
Énoncé
Pour chacune de ces quatre fonctions, dire si l'appel récursif est terminal, et en déduire la profondeur de pile.
(* 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)Corrigé
- A : non terminal. Après le retour de
longueur r, il reste à ajouter : l'activation doit survivre à son appel. Profondeur . - B : terminal. Dans la branche
else, le résultat decherche x rest rendu tel quel. Leifn'y change rien : le résultat de la branche choisie est le résultat de la fonction. Espace . - C : terminal. C'est la forme à accumulateur : tout le calcul se fait avant l'appel, dans l'argument. Espace .
- D : non terminal. Il reste la multiplication par . Profondeur .
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.
