“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 129 — #139
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
129
Ce programme a un deuxième défaut : la taille de la pile grandit avec la longueur de
l’entrée. Il définit un calcul récursif qui n’est pas itératif. Suivre naïvement la définition
récursive de l’inverse nous a donné un programme assez mauvais ! Heureusement, il y
a des techniques simples pour éliminer ces deux défauts. Nous verrons une technique
importante : la transformation d’état.
d) La conversion d’un calcul récursif en calcul itératif
Nous allons convertir un calcul récursif en calcul itératif. Au lieu de Reverse,
prenons une fonction plus simple qui calcule la longueur d’une liste :
fun {Length Xs}
case Xs of nil then 0
[] _|Xr then 1+{Length Xr} end
end
Cette fonction a la même structure que la fonction SumList. Comme SumList, elle
a un temps linéaire mais la taille de la pile est proportionnelle à la profondeur de la
récursion, qui est égal à la longueur de Xs. Ce problème vient du fait que l’addition
1+{Length Xr} est faite après l’appel récursif. L’appel récursif n’est pas le dernier
appel, donc l’environnement de la fonction ne peut pas être récupéré à l’appel.
Comment pouvons-nous calculer la longueur de la liste avec un calcul itératif ? Pour
faire cela, nous devons formuler le problème comme une séquence de transformations
d’état. Nous commençons avec un état S 0 et nous le transformons successivement,
obtenant S 1 , S 2 , . . . , jusqu’à ce que nous arrivions à l’état final S final , qui contient
la réponse. Pour calculer la longueur de la liste, nous allons prendre comme état la
longueur i de la partie de la liste déjà vue. En fait, ce n’est qu’une partie de l’état. Le
reste de l’état est la partie Ys de la liste non encore rencontrée. L’état complet S i est
donc la paire (i, Ys). Le cas général pour l’état intermédiaire S i est (si la liste Xs est
[e 1 e 2 · · · e n ]) :
Xs
e 1 e 2 · · · e i e i+1 · · · e n
Ys
À chaque appel récursif, i sera augmenté de 1 et Ys diminué d’un élément. Cela nous
donne la fonction suivante :
fun {IterLength I Ys}
case Ys of nil then I
[] _|Yr then {IterLength I+1 Yr} end
end
Son type est fun {$ Int List} : Int. Remarquez la différence entre les deux
définitions. Ici l’addition I+1 est faite avant l’appel récursif à IterLength, qui est
le dernier appel. Nous avons défini un calcul itératif.
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
129
Ce programme a un deuxième défaut : la taille de la pile grandit avec la longueur de
l’entrée. Il définit un calcul récursif qui n’est pas itératif. Suivre naïvement la définition
récursive de l’inverse nous a donné un programme assez mauvais ! Heureusement, il y
a des techniques simples pour éliminer ces deux défauts. Nous verrons une technique
importante : la transformation d’état.
d) La conversion d’un calcul récursif en calcul itératif
Nous allons convertir un calcul récursif en calcul itératif. Au lieu de Reverse,
prenons une fonction plus simple qui calcule la longueur d’une liste :
fun {Length Xs}
case Xs of nil then 0
[] _|Xr then 1+{Length Xr} end
end
Cette fonction a la même structure que la fonction SumList. Comme SumList, elle
a un temps linéaire mais la taille de la pile est proportionnelle à la profondeur de la
récursion, qui est égal à la longueur de Xs. Ce problème vient du fait que l’addition
1+{Length Xr} est faite après l’appel récursif. L’appel récursif n’est pas le dernier
appel, donc l’environnement de la fonction ne peut pas être récupéré à l’appel.
Comment pouvons-nous calculer la longueur de la liste avec un calcul itératif ? Pour
faire cela, nous devons formuler le problème comme une séquence de transformations
d’état. Nous commençons avec un état S 0 et nous le transformons successivement,
obtenant S 1 , S 2 , . . . , jusqu’à ce que nous arrivions à l’état final S final , qui contient
la réponse. Pour calculer la longueur de la liste, nous allons prendre comme état la
longueur i de la partie de la liste déjà vue. En fait, ce n’est qu’une partie de l’état. Le
reste de l’état est la partie Ys de la liste non encore rencontrée. L’état complet S i est
donc la paire (i, Ys). Le cas général pour l’état intermédiaire S i est (si la liste Xs est
[e 1 e 2 · · · e n ]) :
Xs
e 1 e 2 · · · e i e i+1 · · · e n
Ys
À chaque appel récursif, i sera augmenté de 1 et Ys diminué d’un élément. Cela nous
donne la fonction suivante :
fun {IterLength I Ys}
case Ys of nil then I
[] _|Yr then {IterLength I+1 Yr} end
end
Son type est fun {$ Int List} : Int. Remarquez la différence entre les deux
définitions. Ici l’addition I+1 est faite avant l’appel récursif à IterLength, qui est
le dernier appel. Nous avons défini un calcul itératif.
© Dunod – La photocopie non autorisée est un délit