La Récursivité
Dans le corps d'un let les identificateurs (noms de
fonctions) sont cherchés dans
l'environnement courant.
La construction
let rec
introduit un identificateur récursif.
Soit Ec
l'environnement courant, la déclaration
let rec foo = E
crée une valeur Vfoo qui est le
résultat de l'évaluation de l'expression E dans l'environnement
Efoo=ë(foo=Vfoo)<|Ecû où E -Efoo-> Vfoo
et Efoo devient l'environnement courant.
let rec fib = function n -> match n with
| 0 -> 0
| 1 -> 1
| _ -> fib(n-1) + fib(n-2) ;;
définit un environnement Efib, une fermeture
Ffib=«n:-> Efib,Efib»
l'évaluation d'une fonction récursive se fait comme une évaluation normale.
À l'appel d'une fonction récursive, il faut empiler les
environnements :
-
Soit Efib l'environnement de définition de fib et E
l'environnement courant.
-
Évaluation de fib(3) dans E :
Ffib(3) puisque fib -E-> Ffib et
3 -E-> 3. On évalue
E3 =fib(n-1) + fib(n-2)
dans E3 =ë(n=3)<|Efibû,
évaluation de fib(2) dans E3 en suspens et :
-
évaluation de fib(1) dans E3 soit l'évaluation de Ffib(1)
qui vaut 1. Donc fib(1) -E3-> 1
- reprise de l'évaluation de fib(2) dans E3 :
évaluation de Ffib(2) puisque
fib -E3-> Ffib et
2 -E3-> 2
On doit évaluer
E2 = fib(n-1) + fib(n-2)
dans E2 = ë(n=2)<|Efibû :
-
évaluation de fib(0) dans E2 soit 0
- évaluation de fib(1) dans E2 soit 1
-
Donc E2 -E2-> 1
- et enfin
E3 -E3-> 2