Récursion terminale
L'enveloppe d'un appel récursif est l'ensemble des calculs qui doivent
d'effectuer après cet appel.
Lors d'un appel récursif, les différents environnements doivent être conservés
car d'autres calculs doivent s'exécuter après :
let rec foo = function n -> match n with
| 0 -> 2
| _ -> foo(n-1) + n;;
Soit E l'environnement courant, si
foo -E-> Ffoo,
Ffoo =«n:-> Efoo,Efoo»
Pour évaluer foo(1) dans E, on doit évaluer Ffoo(1) et donc
évaluer (foo(n-1) + n) dans E1 =ë(n=1)<|Efooû. Si foo(n-1) est évalué en premier il faut restaurer E1 pour
évaluer n.
Un appel récursif est terminal s'il n'y a pas d'autres calculs à
effectuer ensuite. Le résultat de la fonction est alors lui même un
appel récursif.
let rec foo_bis =
function n -> function res -> match n with
| 0 -> res
| _ -> foo_bis (n-1) (res + n);;
" xFfoo(x) = (Ffoo_bisx2)
Si (n -En+1-> n) et
(res -En+1-> r)
il est inutile de stocker En+1 pour déterminer la valeur de
foo_bis (n-1) (res + n) dans En+1
puisque ((n-1) -En+1-> n-1) et
((res + n) -En+1-> r+n) peuvent être calculés
avant