Sommaire
Exemple de programmation impérative : boucle for
Boucle while
Fonctions récursives
Fonctions récursives terminales
Fonction impérative ou récursive ?
Le filtrage par motif

I) Exemple de programmation impérative : boucle for
Dans cette page, nous allons voir les différentes manières de programmer la fonction factorielle en Caml (enfin une fonction utile dans mes exemples !). La première définition mathématique de n! est le produit des n premiers entiers (non nuls). On peut donc calculer n! ainsi : on crée une variable « nombre » valant 1, puis on multiplie cette variable par tous les entiers de 1 à n, successivement. Autrement dit, on fait varier un indice i de 1 à n et pour chaque i, on multiplie nombre par i.
En Caml, la variable nombre se traduira pas une référence, car il s'agit d'une valeur qui doit être modifiée. Quand à la boucle (i varie de 1 à n), elle se traduit par une boucle for : cet opérateur a pour syntaxe « for (1) = (2) to (3) do (...) done; » avec la légende :
   (1) représente le nom de l'indice qui varie, ici i
   (2) représente la valeur de départ de l'indice, ici 1
   (3) représente la valeur finale de l'indice, ici n
   (...) représente l'ensemble des instructions qui doivent être exécutées à chaque itération, selon la valeur de i.
Caml réalise alors les opérations suivantes :
   - il exécute la fonction jusqu'à tomber sur l'opérateur for
   - il crée une variable i à laquelle il affecte la valeur 1
   - il exécute toutes les instructions comprises entre do et done, avec la valeur i = 1
   - arrivé à « done », il augmente la valeur de i de 1 et recommence les instructions entre do et done, avec la nouvelle valeur de i.
   - il recommence jusqu'à atteindre la dernière valeur de i. Arrivé à cette valeur, il exécute une dernière fois les instructions, mais il arrête la boucle et reprend l'exécution du programme après le « done » (et au passage, il détruit la variable i qui n'avait qu'une utilisation locale).
Note : on a ici utilisé « to » entre les deux valeurs limites parce que la valeur terminale (n) est plus grande que la valeur initiale (1). Il est possible de le faire dans l'autre sens (faire varier i de n à 1) mais on doit alors remplacer to par downto.
D'où la fonction :
let factorielle n =
let nombre = ref 1 in
for i = 1 to n do
   nombre := (!nombre * i)
done;
!nombre;;
Ou dans l'autre sens :
let factorielle n =
let nombre = ref 1 in
for i = n downto 1 do
   nombre := (!nombre * i)
done;
!nombre;;

II) Boucle while
Les boucles for sont très pratiques, mais la programmation impérative peut se faire à l'aide d'une autre boucle, while (tant que). La syntaxe est la suivante : « while (1) do (...) done; » où (1) représente une condition (donc une expression dont le résultat est un booléen) et (...) une liste d'instructions. Lorsque Caml rencontre l'opérateur while, il teste si (1) est vrai. Si c'est le cas, il exécute les instructions (...) et revient au « while ». Il continue tant que la condition (1) est vraie (d'où le nom « tant que »). Dès que (1) est faux, Caml saute les instructions (...) et reprend après « done ».
On veillera à ce qu'il y ait bien une fin : la condition ne doit pas être toujours vraie, sinon quoi le programme ne s'arrêtera jamais (et l'ordinateur plantera).

III) Fonctions récursives
n! est défini d'une autre manière : par récurrence. En effet, n! = n.(n-1)! On peut donc calculer n! d'une autre manière : si n vaut 1, on rend 1. Sinon, on rend le produit de n par (n-1)! C'est ce qu'on appelle une fonction récursive : elle fait appel à elle-même ! Mais il y a un problème. Essayons :
let factorielle_recursive n = if n = 1 then 1 else n*(factorielle_recursive (n-1));;
Caml déclenche une erreur. Il dit que la valeur « factorielle_recursive » n'est pas définie. Et c'est vrai ! Tant que les deux points-virgules ne sont pas atteints, la fonction factorielle_recursive n'existe pas, on ne peut pas faire appel à elle. Mais alors, comment faire du récursif ? Il suffit de remplacer « let » par « let rec », sans modifier le reste : on indique ainsi à Caml que la fonction qui va être définie est récursive.
let rec factorielle_recursive n = if n = 1 then 1 else n*(factorielle_recursive (n-1));;
Comme pour la boucle while, il faut veiller à ne pas faire de boucle infinie en s'assurant de deux choses :
- il doit y avoir au moins un « cas terminal », c'est-à-dire une valeur possible de l'argument pour laquelle la fonction rendra un résultat sans s'appeler elle-même. Il est possible de définir plusieurs cas terminaux.
- il faut ensuite s'assurer que quelque soit l'argument avec lequel on pourra appeler la fonction, l'exécution de la fonction finira bien par retomber sur un des cas terminaux.

IV) Fonctions récursives terminales
Là, on commence à entrevoir un sujet plus compliqué de l'informatique : la complexité, c'est-à-dire la réflexion sur la qualité d'un algorithme par rapport aux ressources qu'il demande. En termes d'occupation de la mémoire, cette fonction (factorielle_recursive) n'est pas très bonne. En effet, lorsque vous demandez n!, Caml garde n en mémoire, puis appelle (n-1)!. Alors il garde (n-1) en mémoire et appelle (n-2)!. Il continue jusqu'à 1. Et alors il fait le produit de 1 par 2, puis par 3, ainsi de suite jusqu'à (n-1) puis n. Autrement dit, Caml fait tous les appels récursifs d'abord puis calcule après. C'est mauvais car pendant l'exécution, il va devoir garder en mémoire n nombres. Ici, ce n'est pas très grave mais sur des fonctions plus complexes agissant sur des données importantes en taille, ça peut poser des problèmes !
Comment améliorer cela ? On va forcer Caml à d'abord multiplier avant de faire la récurrence. C'est ce qu'on appelle une récurrence terminale : la récurrence est à la fin. Caml ne conserve ainsi jamais rien en mémoire. Dans le cas de la factorielle, on procède ainsi : notre nouvelle fonction va avoir deux arguments, n ainsi que les produits intermédiaires.
   - La fonction prend en argument n et produits
   - Elle rajoute n dans produits et recommence (la récurrence est ici) avec n-1.
   - Quand on arrive à n = 1, on rend produits.
let rec factoriellebis n produits = if n = 1 then produits else factoriellebis (n-1) (n*produits);;
Et alors, pour obtenir n! il suffit de taper factoriellebis n 1. Cela dit, ce n'est pas très pratique ! Il serait mieux de ne donner que n pour avoir la factorielle, autrement dit avoir une fonction à un argument. Pour faire cela en gardant la récurrence terminale, on utilise la fonction précédente comme fonction auxiliaire (c'est une définition locale) d'une autre fonction :
let super_factorielle n =
   let rec aux i produits = if i = 1 then produits else aux (i-1) (i*produits) in
aux n 1;;

V) Fonction impérative ou récursive ?
Il est beaucoup plus dans l'esprit de Caml d'utiliser des fonctions récursives : cela correspond plus à sa définition. D'ailleurs, certains enseignants ne parlent pas du tout ce qui est boucles for, boucles while, références (qui deviennent inutiles en récursif), ... De même, certaines écoles d'ingénieurs interdisent dans leurs concours d'entrée l'emploi de ces méthodes. De toute façon, les fonctions récursives peuvent au début sembler plus compliquées que les fonctions impératives, mais avec l'habitude on les préfère.
En revanche, la récurrence terminale reste un détail. Si vous n'avez pas tout compris, ne vous en faites pas. C'est mieux mais pas indispensable. De toute façon, les problèmes de complexité ne concernent que des programmes très poussés.
Attention : je n'ai pas dit qu'il ne faut faire que du récursif et bannir l'impératif ! Le style impératif est parfois bien plus pratique, par exemple pour calculer sur des matrices, ou tracer 20 lignes parallèles à l'écran... En fait, une des forces de Caml est qu'on peut mixer dans un même programme le style récursif et le style impératif, ce qui donne une certaine souplesse.

VI) Le filtrage par motif
Reprenons la fonction factorielle_recursive. Le test « if n = 1 then ... else ... » peut être codé autrement, en utilisant ce qu'on appelle un filtrage. Sa syntaxe est la suivante :
« match (1) with
|(2) -> (3)
|..... »
   (1) représente le nom de ce qui sert au filtrage. Ici, ce sera n
   (2) représente la première possibilité pour (1), c'est ce qu'on appelle un motif. Ici, n peut valoir 1
   (3) représente ce que Caml doit faire si (1) correspond au motif (2)
   On continue ainsi, vous pouvez faire autant de lignes que vous le voulez, en les commençant toutes par une barre verticale (tapez Alt Gr + 6).
Caml procède ainsi : il teste si (1) correspond au motif (2). Si c'est le cas, il fait ce qui suit la flèche et ne regarde pas les autres cas. Sinon, il regarde la deuxième ligne et ainsi de suite. Le dernier cas est souvent représenté par _ (touche 8). Cette barre signifie « tout ce qui reste », c'est la poubelle de ce qui n'est pas dans les cas précédents du filtrage.
Ici, on peut utiliser un filtrage :
let rec factorielle_recursive n = match n with
   |1 -> 1
   |_ -> n*(factorielle_recursive (n-1));;
C'est beaucoup plus lisible, non ? Bien entendu, le filtrage n'est ici pas très utile, je voulais l'introduire sur un exemple simple. Toutefois, il peut être très pratique dans d'autres cas. Par exemple, vous avez une fonction quelconque agissant sur une liste nommée li. Vous voulez faire plusieurs cas : soit la liste est vide, et vous faites quelque chose, soit elle n'est pas vide, et alors vous agissez différemment sur sa tête (List.hd li) et sa queue (List.tl li) :
let (rec) fonction li = ........ match li with
   |[] -> ...........
   |t::q -> ..............
;;
Dans le deuxième cas, vous n'aurez pas besoin après la flèche d'utiliser les fonctions List.hd et List.tl pour désigner la tête et la queue : grâce au filtrage par « t::q », Caml les a déjà nommées : t = List.hd li et q = List.tl li.
Je vous conseille de voir des exemples dans les exercices ou les exemples de fonctions simples pour tout comprendre sur le filtrage. Bien entendu, l'usage du filtrage n'est absolument pas réservé aux fonctions récursives ! Signalons enfin que l'usage d'un cas « poubelle » désigné par « _ » n'est pas obligatoire : vous pouvez créer un filtrage qui ne prévoit pas tous les cas, si vous êtes sûr(e) que pour l'usage que vous ferez ensuite de votre fonction, les cas restants ne seront pas nécessaires. Si vous faites ça, Caml vous fournira un avertissement, disant que votre filtrage n'est pas exhaustif. Ce message qu'il vous donne n'est pas une erreur : votre fonction sera quand même définie (si le reste est bon, du moins). C'est plutôt une manière polie qu'a Caml de vous demander si vous êtes certain(e) de ne rien avoir oublié.

> Haut de la page