“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 3 — #13
i
i
i
i
i
i
i
i
1.3 Les fonctions
3
1.3 LES FONCTIONS
Faisons maintenant un calcul plus compliqué. Supposons que nous voulions calculer
la fonction factorielle n!, que l’on peut définir comme 1 × 2 × · · · × (n − 1) × n. C’est
le nombre de permutations de n objets, c’est-à-dire le nombre de manières différentes
de les placer dans une séquence. La factorielle de 10 est :
{Browse 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10}
Il s’affiche alors 3628800. Que faire pour calculer la factorielle de 100 ? Nous
voudrions que le système fasse le travail encombrant de taper tous les entiers de 1 à
100. Nous faisons plus : nous expliquons au système comment calculer la factorielle
pour tout n. Nous le faisons en définissant une fonction :
declare
fun {Fact N}
if N==0 then 1 else N * {Fact N-1} end
end
L’instruction declare crée la nouvelle variable Fact. L’instruction fun définit une
fonction. La variable Fact est liée à la fonction. La fonction a un argument N, qui est
une variable locale, c’est-à-dire qu’elle n’est connue que dans le corps de la fonction.
Chaque fois que nous appelons la fonction, une nouvelle variable est créée.
La récursion
Le corps de la fonction est une instruction appelée expression if. Quand la fonction
est appelée, l’expression if fait les choses suivantes :
– Elle teste d’abord si N est égal à 0 en faisant le test N==0.
– Si le test réussit, l’expression juste après le then sera calculée. Cela renvoie le
nombre 1, parce que la factorielle de 0 est 1.
– S’il échoue, l’expression juste après le else sera calculée. Si N n’est pas 0,
l’expression N * {Fact N-1} sera calculée. Cette expression utilise Fact, la
même fonction que nous sommes en train de définir ! Cette technique s’appelle
la récursion. C’est parfaitement normal et ne devrait pas nous inquiéter.
Fact se base sur la définition mathématique suivante de la factorielle :
0! = 1
n! = n × (n − 1)! if n > 0
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
1.3 Les fonctions
3
1.3 LES FONCTIONS
Faisons maintenant un calcul plus compliqué. Supposons que nous voulions calculer
la fonction factorielle n!, que l’on peut définir comme 1 × 2 × · · · × (n − 1) × n. C’est
le nombre de permutations de n objets, c’est-à-dire le nombre de manières différentes
de les placer dans une séquence. La factorielle de 10 est :
{Browse 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10}
Il s’affiche alors 3628800. Que faire pour calculer la factorielle de 100 ? Nous
voudrions que le système fasse le travail encombrant de taper tous les entiers de 1 à
100. Nous faisons plus : nous expliquons au système comment calculer la factorielle
pour tout n. Nous le faisons en définissant une fonction :
declare
fun {Fact N}
if N==0 then 1 else N * {Fact N-1} end
end
L’instruction declare crée la nouvelle variable Fact. L’instruction fun définit une
fonction. La variable Fact est liée à la fonction. La fonction a un argument N, qui est
une variable locale, c’est-à-dire qu’elle n’est connue que dans le corps de la fonction.
Chaque fois que nous appelons la fonction, une nouvelle variable est créée.
La récursion
Le corps de la fonction est une instruction appelée expression if. Quand la fonction
est appelée, l’expression if fait les choses suivantes :
– Elle teste d’abord si N est égal à 0 en faisant le test N==0.
– Si le test réussit, l’expression juste après le then sera calculée. Cela renvoie le
nombre 1, parce que la factorielle de 0 est 1.
– S’il échoue, l’expression juste après le else sera calculée. Si N n’est pas 0,
l’expression N * {Fact N-1} sera calculée. Cette expression utilise Fact, la
même fonction que nous sommes en train de définir ! Cette technique s’appelle
la récursion. C’est parfaitement normal et ne devrait pas nous inquiéter.
Fact se base sur la définition mathématique suivante de la factorielle :
0! = 1
n! = n × (n − 1)! if n > 0
© Dunod – La photocopie non autorisée est un délit