“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 121 — #131
i
i
i
i
i
i
i
i
3.3 Le calcul récursif
121
proc {Fact N ?R}
if N==0 then R=1
elseif N>0 then N1 R1 in
N1=N-1
{Fact N1 R1}
R=N * R1
else raise domainError end end
end
Déjà on peut deviner que la taille de la pile pourrait grandir puisqu’il y a une multiplication après l’appel récursif. Pendant l’appel récursif la pile doit garder des informations
pour pouvoir faire cette multiplication quand l’appel revient. En suivant la sémantique
nous pouvons voir ce qui se passe pendant l’appel {Fact 5 R}. Pour la clarté, nous
simplifions légèrement la présentation de la machine abstraite en substituant la valeur
d’une variable dans l’environnement. L’environnement {. . . , N → n, . . .} sera donc
écrit comme {. . . , N → 5, . . .} si la mémoire est {. . . , n = 5, . . .}.
– La pile sémantique initiale est [({Fact N R}, {N → 5, R → r 0 })].
– Au premier appel récursif :
[({Fact N1 R1}, {N1 → 4, R1 → r 1 , . . .}),
(R=N * R1, {R → r 0 , R1 → r 1 , N → 5, . . .})]
– Au deuxième appel récursif :
[({Fact N1 R1}, {N1 → 3, R1 → r 2 , . . .}),
(R=N * R1, {R → r 1 , R1 → r 2 , N → 4, . . .}),
(R=N * R1, {R → r 0 , R1 → r 1 , N → 5, . . .})]
– Au troisième appel récursif :
[({Fact N1 R1}, {N1 → 2, R1 → r 3 , . . .}),
(R=N * R1, {R → r 2 , R1 → r 3 , N → 3, . . .}),
(R=N * R1, {R → r 1 , R1 → r 2 , N → 4, . . .}),
(R=N * R1, {R → r 0 , R1 → r 1 , N → 5, . . .})]
Il est clair que la pile grandit d’une instruction à chaque appel récursif. Le dernier appel
récursif est le cinquième, qui retourne tout de suite avec r 5 = 1. Cinq multiplications
sont faites ensuite pour obtenir le résultat final r 0 = 120.
3.3.2 Une machine abstraite basée sur les substitutions
Cet exemple montre que la machine abstraite du chapitre 2 est encombrante pour le
calcul à la main. C’est parce qu’elle garde les identificateurs en utilisant des environnements pour faire la correspondance avec les variables. Cette approche est réaliste ; c’est
© Dunod – La photocopie non autorisée est un délit