“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 123 — #133
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
123
Dans ce nouvel ordre, le calcul peut être fait incrémentalement, en commençant avec
1 * 5. Cela donne 5. En continuant ainsi, nous obtenons 20, 60, 120 et finalement
120. La définition itérative qui fait ce calcul est
fun {Fact N}
fun {FactIter N A}
if N==0 then A
elseif N>0 then {FactIter N-1 A * N}
else raise domainError end end
end
in {FactIter N 1} end
La fonction qui fait l’itération, FactIter, a un deuxième argument A. Cet argument
est essentiel ; sans un deuxième argument, une factorielle itérative est impossible.
Le deuxième argument n’est pas manifeste dans la définition mathématique de la
factorielle que nous avons utilisée. Il faut un raisonnement pour démontrer son utilité
au programme.
3.4 LA PROGRAMMATION AVEC LA RÉCURSION
Les calculs récursifs sont au cœur de la programmation déclarative. Cette section
explique comment écrire dans ce style. Nous montrons les techniques de base pour la
programmation avec les listes, les arbres et d’autres types de données récursifs. Nous
montrons aussi comment rendre les calculs itératifs quand c’est possible. Cette section
contient les parties suivantes :
– Le premier pas est la définition des types de données récursifs. La section 3.4.1
présente une notation simple qui nous permet de définir les types de données
récursifs les plus importants.
– Le type de données récursif le plus important est la liste. La section 3.4.2 montre
les techniques de base pour programmer avec les listes.
– Les programmes déclaratifs efficaces doivent définir des calculs itératifs. La section 3.4.3 montre les accumulateurs, une technique systématique pour atteindre
ce but.
– Le deuxième type de données récursif le plus important, après les structures
linéaires comme les listes, est l’arbre. La section 3.4.4 montre les techniques de
base pour programmer avec les arbres.
3.4.1 La définition des types
Le type de liste est un sous-ensemble du type d’enregistrement. Il y a d’autres sousensembles utiles de l’enregistrement, comme les arbres binaires. Avant d’écrire des
© Dunod – La photocopie non autorisée est un délit