On a expliqué les fonctions en prenant l'images de robots. Rappelons le principe : lorsque le robot est appelé, il ramasse les objets qui sont posés devant lui, il effectue des actions, puis il dépose éventuellement un objet avant de partir. On pourrait croire que pour chaque fonction, on a un robot qui dort dans un coin, et qu'à chaque fois que la fonction est appelée, on réveil le robot pour qu'il fasse son travail. Eh bien ce n'est pas tout à fait comme cela que ça se passe.

En fait, une fonction, c'est un manuel de fabrication pour un robot. Au début, aucun robot n'est présent. Les robots sont fabriqués dès qu'on a besoin d'eux, et jetés à la poubelle dès qu'on en a plus besoin. La fonction que le programmeur écrit correspond aux plans de constructions du robot. En d'autres termes, lorsqu'on appelle une fonction, un robot est construit, ce robot fait son travail, puis il est détruit. Ce n'est pas très écologique de gaspiller autant de robots, mais comme tout ce qu'on fait est entièrement virtuel, aucune pollution n'est engendrée.

Pour faire son travail, un robot peut faire appel à d'autres robots. Par exemple, la fonction suivant affiche successivement ses deux paramètres qui sont de type int :

let print_2_int x y =
  print_int x;
  print_int y;
  in

Supposons que l'on écrive maintenant print_2_int 9 5. Détaillons ce qui se passe :

1. Un robot A est créé selon le modèle print_2_int. A est donc programmé pour ramasser deux objets et appeler print_int sur chacun d'entre eux.
2. Le robot A est ensuite mis en route. Il ramasse le 9 et le 5.
3. Ensuite, A appelle print_int 9. Pour cela, il pose le 9, et demande la construction d'un robot avec le plan de construction print_int.
1. Un robot B est créé selon le modèle print_int.
2. Le robot B ramasse l'entier 9, et l'affiche.
3. Le robot B a fini son travail, il s'auto-détruit.
4. Après, A appelle print_int 4. Pour cela, il pose le 4, et demande la construction d'un robot avec le plan de construction print_int.
1. Un robot C est créé selon le modèle print_int.
2. Le robot C ramasse l'entier 4, et l'affiche.
3. Le robot C a fini son travail, il s'auto-détruit.
5. Le robot A a fini son travail, il s'auto-détruit.

Il est important de noter qu'il n'y a aucune relation entre le robot B, qui affiche le 9, et le robot C, qui affiche le 4, si ce n'est qu'ils ont été fabriqué tous deux selon le même plan de fabrication, à savoir la fonction print_int.

Un robot peut donc appeler d'autres robots. Dans l'exemple qui précède, un robot programmé selon la fonction print_2_int appelait des robots programmés selon la fonction print_int.

Maintenant, il est possible qu'un robot, pour effectuer sont travail, fasse appel à un autre robot qui soit programmé de la même manière. Traduit en termes de fonctions, cela donne :

Une fonction récursive est une fonction qui s'appelle elle-même.

Voyons tout de suite un exemple. On va fabriquer un robot qui ramasse un entier n, et qui va calculer la valeur de la factorielle de n, c'est on le rappelle le produit des n premiers entiers. On sait déjà coder ça avec des boucles for ou while, mais cette fois on va faire sans. Pour cela, on va partir du principe que le produit des entiers compris entre 1 et n est égal à n fois le produit des entiers compris entre 1 et n-1.

Pour calculer factorielle de n, notre robot va donc procéder en deux étapes. D'abord il va faire appel à un robot assistant (un robot distinct, mais programmé pareil) pour calculer factorielle de (n - 1). Ensuite il va multiplier le résultat obtenu par n, et retourner le résultat.

il utilise encore un autre robot assistant, qui sera chargé de calculer la factorielle de (n - 2), puis il multiplie le résultat par (n - 1). Mais quand cela s'arrête-t-il ? Au bout

On peut maintenant écrire le plan de fabrication de notre robot, c'est-à-dire la fonction récursive factorielle :

let factorielle n =
  if n = 1
     then 1
     else n * (factorielle (n-1))
  in

• La fonction prend un entier n en argument.
• Si n vaut 1, alors on retourne 1.
• Sinon, on retourne n fois la factorielle de n - 1.

Si on rajoute une comme print_int (factorielle 5) et qu'on essaie de compiler, on obtient un message d'erreur :

File "test.ml", line 4, characters 16-27:
Unbound value factorielle

L'erreur se situe au niveau du nom factorielle qui se situe dans le corps de la fonction factorielle. Cette erreur est normale : on est en train de définir la fonction factorielle, donc elle n'est pas encore définie. Pour résoudre ce problème, il suffit de rajouter le mot clé rec juste après le let. Il permet d'indiquer que l'on définit une fonction récursive. Maintenant :

let rec factorielle n =
  if n = 1
     then 1
     else n * (factorielle (n-1))
  in

print_int (factorielle 5);

le code compile et s'exécute correctement, affichant le résultat 120.

Pour définir une fonction récursive, on place le mot clé rec entre le let et le nom de la fonction.

On peut suivre l'ordre d'appel des fonctions en ajoutant un print_int n tout au début du corps de la fonction. Ainsi :

let rec factorielle n =
  print_int n;
  print_string " ";
  if n = 1
     then 1
     else n * (factorielle (n-1))
  in

print_int (factorielle 5);