Jusqu'à maintenant, ce que vous pouviez coder était en réalité assez limité. Si vous avez déjà programmé avant, vous vous demandez peut-être où sont les boucles. Dans ce chapitre, vous allez apprendre à utiliser la récursivité pour écrire des programmes qui font des choses que vous ne savez pas encore faire.
C'est quoi ?
La récursivité
Exemple : la fonction factorielle
La factorielle de n (notée $n!$) est le produit de tous les nombres de 1 à n. Vous avez déjà vu un moyen de coder cette fonction, en utilisant la fonction product : fac n = product [1..n]. Pour montrer l'intérêt de la récursivité, nous allons maintenant essayer de coder cette fonction sans utiliser de fonctions prédéfinies, mais seulement quelques opérations de base.
Pour cela, on va utiliser une propriété de la factorielle : on a $n!=1 \times 2 \times \cdots \times (n-1) \times n = n \times (1\times 2 \times \cdots \times (n-1)) = n \times (n-1)!$. En résumé, cela donne : $n!=n\times (n-1)!$. Cette propriété est intéressante, car elle nous permet de calculer $n!$ à partir de $(n-1)!$. Donc, pour pouvoir calculer $n!$, il suffit de savoir calculer $(n-1)!$, donc de savoir calculer $(n-2)!$, et ainsi de suite. Cependant, si on ne fait que répéter à l'infini cette méthode, le calcul ne donnera jamais de résultat. Pour cela, il faut définir un cas pour lequel on donne immédiatement le résultat. On dira donc que $1!=1$, et à partir de ce résultat, on peut calculer $n!$ pour tout $n \ge 1$.
Pour coder la fonction factorielle en Haskell, on fera exactement la même chose :
1 2 | fac 1 = 1 fac n = n * fac (n-1) |
Ici, comme on utilise le filtrage de motif, seul le premier motif qui correspond sera utilisé pour faire le calcul : l'ordre des lignes est donc important. Cette fonction est un exemple de fonction récursive, car elle s'appelle elle-même. Quand la fonction fac est exécutée, il se passe quelque chose qui ressemble à cela :
1 2 3 4 5 6 7 8 9 10 11 12 | calculer fac 4: la définition "fac n = n * fac (n-1)" est la première qui correspond j'ai besoin de fac 3: la définition "fac n = n * fac (n-1)" est la première qui correspond j'ai besoin de fac 2: la définition "fac n = n * fac (n-1)" est la première qui correspond j'ai besoin de fac 1: la définition "fac 1 = 1" est la première qui correspond fac 1 vaut 1 je multiplie par 2, fac 2 vaut 2 je multiplie par 3, fac 3 vaut 6 je multiplie par 4, fac 4 vaut 24 |
Utiliser la récursivité
L'idée que l'on applique souvent pour coder une fonction récursive est de rapporter un problème (calculer $n!$) à un ou plusieurs problèmes plus faciles (calculer $(n-1)!$). On n'est donc pas obligé d'enlever un à chaque fois : par exemple, on va coder une fonction qui calcule le pgcd de deux nombres. Si vous êtes déjà allés en troisième, vous devez connaître l'algorithme d'Euclide. Il se base sur la propriété suivante : quand on écrit la division euclidienne de a par b, $a = bq+r$, on a : $pgcd(a,b)=pgcd(b,r)$. Il suffit donc à chaque étape de diviser le nombre le plus petit par le plus grand, jusqu'à se ramener à un cas donc le pgcd est très facile à calculer : celui où un des deux nombres divise l'autre. En fait, on remarque que quand un des nombres divise l'autre, à la prochaine étape, le reste vaudra 0, et donc on aura à calculer le pgcd d'un nombre et 0, qui est ce nombre (pour que cela reste cohérent).
1 2 3 4 5 | pgcd 0 k = k pgcd k 0 = k pgcd a b = pgcd c (d `mod` c) where d = max a b c = min a b |
À chaque étape, on diminue le maximum des deux nombres : on se ramène donc bien à chaque fois à un cas plus simple à résoudre.
Parfois, on n'arrive pas tout de suite à trouver comme faire quelque chose de façon récursive. Par exemple, arrivez-vous à coder une fonction récursive qui donne le plus petit diviseur (plus grand que 1) d'un nombre donné ? On ne voit pas sur quoi faire la récursivité dans ce cas-là : quels seraient les sous-problèmes ?
En fait, telle quelle, cette fonction ne peut pas être définie de manière récursive. Par contre, on peut trouver une fonction qui fait plus de choses, et qui se définit bien par récurrence. On va donc définir la fonction diviseurPlusGrandQue qui donne le plus petit diviseur d'un nombre plus grand ou égal à un autre nombre (par exemple, diviseurPlusGrandQue 12 5 donne 6, car 6 divise 12 et 6 est plus grand que 5). Il est très facile de coder plusPetitDiviseur" à partir de cette fonction :
1 | plusPetitDiviseur n = diviseurPlusGrandQue n 2 |
Il ne nous reste plus qu'à coder la fonction diviseurPlusGrandQue. Appelons n le nombre dont on doit trouver un diviseur, et d la valeur minimale du diviseur (le diviseur doit être plus grand que d). On obtient donc le code suivant :
1 2 3 4 5 | d `divise` n = n `mod` d == 0 diviseurPlusGrandQue n d | d `divise` n = d | otherwise = diviseurPlusGrandQue n (d+1) |
Cette fonction a une propriété intéressante : regardons comment se passe le calcul de diviseurPlusGrandQue 35 2 :
1 2 3 4 5 6 7 8 9 10 11 | calculer diviseurPlusGrandQue 35 2: 2 ne divise pas 35, on doit calculer diviseurPlusGrandQue 35 3 calculer diviseurPlusGrandQue 35 3: 3 ne divise pas 35, on doit calculer diviseurPlusGrandQue 35 4 calculer diviseurPlusGrandQue 35 4: 4 ne divise pas 35, n doit calculer diviseurPlusGrandQue 35 5 calculer diviseurPlusGrandQue 35 5: 5 divise 35, on retourne 5 on retourne le résultat : 5 on retourne le résultat : 5 on retourne le résultat : 5 |
Récursion terminale
Quand on calcule diviseurPlusGrandQue, à chaque étape, après avoir appelé la fonction suivante, on ne fait que retourner le résultat. Dans ce cas, il n'y a pas besoin de retenir d'informations sur la pile sur ce que la fonction doit faire après l'appel, puisqu'elle retourne juste la valeur renvoyée par la fonction appelée. Dans ce cas, le compilateur est capable d'appliquer une optimisation, qui fait que le code est plutôt exécuté de cette façon :
1 2 3 4 5 | calculer diviseurPlusGrandQue 35 2: 2 ne divise pas 35, on doit calculer diviseurPlusGrandQue 35 3 3 ne divise pas 35, on doit calculer diviseurPlusGrandQue 35 4 4 ne divise pas 35, on doit calculer diviseurPlusGrandQue 35 5 5 divise 35, donc le résultat est 5 |
On dit que cette fonction est tail-recursive, car l'appel récursif est la dernière chose faite par la fonction. Certaines fonctions peuvent être réécrites de manière tail-recursive en utilisant un accumulateur. C'est le cas de la fonction factorielle :
1 2 3 4 | fac n = fac' n 1 fac' 1 acc = acc fac' n acc = fac' (n-1) (n*acc) |
Si vous calculez le résultat dans votre tête, vous vous apercevrez que cette fonction donne bien $n!$, et elle est tail-récursive. On a réussi à écrire fac de façon tail-récursive, mais cela n'est pas possible pour toutes les fonctions. La tail-récursivité peut améliorer légèrement les performances (car le compilateur est capable de transformer l'appel récursif en boucle), mais interagit assez mal avec l'évaluation paresseuse. En général, il ne faut pas essayer de toujours réécrire une fonction de façon tail-recursive, mais préférer la forme la plus naturelle à écrire et la plus lisible. Par exemple, pour plusPetitDiviseur, il est naturel de formuler le calcul de cette façon, mais la définition tail-recursive de fac est moins claire que la définition du début du chapitre.
Filtrage de motif et récursivité
Cette sous-partie va vous montrer comment on utilise la récursivité pour manipuler les listes. En effet, les listes sont définies de manière récursive : le constructeur :, pour créer une liste prend un élément et… une liste. Il est donc naturel d'utiliser la récursivité pour parcourir une liste.
Parcourir des listes
Longueur d'une liste
Pour illustrer cette idée, on va commencer par un exemple pas trop compliqué : comment calculer la longueur d'une liste ?
On sait que la longueur d'une liste vide est 0. De plus, quand une liste est de la forme x:xs, sa longueur est la longueur de xs plus 1. On obtient donc le code suivant :
1 2 | longueur [] = 0 longueur (x:xs) = 1 + longueur xs |
On va voir comment s'exécute ce code (ici, = veut dire "revient à calculer à") :
longueur (1:2:3:[]) = 1 + longueur (2:3:[]) = 1 + (1 + longueur (3:[])) = 1 + ( 1 + (1 + longueur [])) = 1 + (1 + (1 + 0)) = 1 + (1 + 1) = 1 + 2 = 3
Et voilà, ce code calcule bien la longueur d'une liste. Le code de la plupart des fonctions sur les listes que vous coderez ressemblera à celui-là.
Plus d'exemples ?
Par exemple, comment calculeriez-vous la somme des éléments d'une liste (par convention, la somme des éléments d'une liste sans éléments est 0) ? Réfléchissez bien, vous devriez pouvoir y arriver.
1 2 3 | somme :: (Num a) => [a] -> a somme [] = 0 somme (x:xs) = x + somme xs |
Vous pouvez aussi coder la fonction produit de la même manière.
De la même façon, vous pouvez coder une fonction monMinimum qui donne l'élément le plus petit d'une liste. Le minimum d'une liste vide n'est pas défini.
1 2 3 | myMinimum :: (Ord a) => [a] -> a myMinimum [x] = x myMinimum (x:xs) = min x (myMinimum xs) |
On peut aussi coder des fonctions qui construisent des listes, toujours de façon récursive. Par exemple, vous devriez pouvoir coder la fonction compter qui prend deux arguments et renvoie la liste des nombres entre ces deux arguments (un équivalent de la notation [a..b]).
1 2 | compter a b | a > b = [] | otherwise = a:compter (a+1) b |
Pourrez-vous, en combinant les idées des deux dernières fonctions, coder une fonction qui ajoute 1 à chaque élément d'une liste ? Et une fonction qui multiplie par 2 chaque élément d'une liste ?
1 2 3 4 5 | ajouter1 [] = [] ajouter1 (x:xs) = (x+1):ajouter1 xs multiplierPar2 [] = [] multiplierPar2 (x:xs) = (2*x):multiplierPar2 xs |
Et maintenant, vous pouvez essayer de coder une fonction supprimer qui prend une liste et un élément, et renvoie une liste où toutes les occurrences de cet élément ont été supprimées.
1 2 3 | supprimer _ [] = [] supprimer el (x:xs) | el == x = supprimer el xs | otherwise = x:supprimer el xs |
Maintenant, pour vous entrainer, vous pouvez essayer de recoder quelques fonctions du Prelude. Par exemple, codez une fonction append qui fait la même chose que ++. Un indice : la récursivité se fait sur la première liste.
Renverser une liste
Vous allez voir ici comment renverser une liste de manière efficace, c'est-à-dire transformer la liste [1,2,3] en [3,2,1]. La version ci-dessous n'utilise pas de concept nouveau et donne le bon résultat.
1 2 | renverser [] = [] renverser (x:xs) = renverser xs ++ [x] |
Cependant, elle est assez inefficace : elle prend environ n² opérations où n est la longueur de la liste. On va donc chercher une version plus efficace. En fait, le problème est qu'on construit la liste dans le mauvais sens, c'est-à-dire en commençant par l'avant (renverser xs) puis en rajoutant un élément à la fin avec ++, ce qui n'est pas du tout efficace. Pourtant, on a toutes les informations pour construire la liste dans l'autre sens. Pour cela, on va créer une fonction renverser' à laquelle on va rajouter un argument suite, qui donne la suite de la liste à construire.
On obtient donc ça :
1 2 | renverser' [] suite = [] ++ suite renverser' (x:xs) suite = renverser' xs [] ++ [x] ++ suite |
Or, la partie [x] ++ suite peut être utilisée comme suite pour l'appel récursif, puisqu'elle doit être appelée à la fin. On obtient donc le code suivant, efficace et récursif terminal. C'est un bon exemple d'un cas où la tail-récursivité donne une formulation naturelle pour la fonction.
1 2 3 4 | renverser l = renverser' l [] renverser' [] suite = suite renverser' (x:xs) suite = renverser' xs (x:suite) |
Application : un tri
Nous allons utiliser tout ce que vous avez vu pour trier des listes. Essayez de coder les fonctions nécessaires sans regarder le code source, mais seulement grâce à la description. Si vous n'y arrivez pas et que vous bloquez, ce n'est pas grave, les solutions sont là.
Tri par insertion
Ce premier tri se base sur l'idée suivante : une liste vide est triée, et pour trier une liste de n+1 éléments, il suffit de trier une liste de n éléments puis d'ajouter le n+1 ème à la bonne position. Pour cela, il faut coder une fonction insertion, qui prend une liste triée dans l'ordre croissant et un élément, et insère l'élément au bon endroit pour que la liste soit triée (c'est-à-dire avant le premier élément plus grand que lui).
1 2 3 | insertion el [] = [el] insertion el (x:xs) | x > el = el:x:xs | otherwise = x:insertion el xs |
Ensuite, pour trier une liste, il suffit de trier la queue de la liste, et d'insérer la tête au bon endroit.
1 2 | triInsertion [] = [] triInsertion (x:xs) = insertion x (triInsertion xs) |
On a donc une première fonction de tri.
Tri fusion
Le tri fusion, plus efficace, se base sur le principe "diviser pour régner" : on découpe la liste à trier en deux listes, qu'on trie chacune indépendamment, puis on regroupe les deux listes triées avec une fonction de fusion. On va commencer par la fonction de fusion : elle prend deux listes triées, et renvoie une liste triée contenant les éléments des deux listes. Pour cela, on procède par récursivité : à chaque étape, on enlève un élément de l'une des deux listes (le minimum des éléments en tête), puis on l'ajoute devant la liste triée formée du reste des éléments.
1 2 3 4 | fusion xs [] = xs fusion [] ys = ys fusion (x:xs) (y:ys) | x >= y = y:fusion (x:xs) ys | y >= x = x:fusion xs (y:ys) |
Ensuite, il faut une fonction pour diviser la liste en deux parties. Elle renvoie une paire de listes, et elle fonctionne de manière récursive en consommant des éléments deux par deux.
1 2 3 | couper [] = ([],[]) couper (x:[]) = ([x],[]) -- et pas (x,[]) car on doit renvoyer une liste couper (x:y:l) = let (xs,ys) = couper l in (x:xs,y:ys) |
Finalement, on combine tout ça pour faire notre fonction de tri :
1 2 3 4 | triFusion [] = [] triFusion [x] = [x] triFusion l = let (xs,ys) = couper l in fusion (triFusion xs) (triFusion ys) |
Et voilà, notre deuxième fonction de tri est terminée. Il faut gérer les cas de la liste vide et de la liste à deux éléments particulièrement, sinon elles seraient coupées respectivement en deux listes vides, et une liste à un élément et une autre vide, et le tri ne se terminerait jamais (vous pouvez exécuter le programme dans votre tête pour tester).
Si vous cherchez plus d'explications sur les algorithmes de tri, vous pouvez lire les cours de la partie algorithmique du site du zéro, ou le tutoriel Algorithmique pour l'apprenti programmeur.
La récursivité est une technique très puissante : elle permet de remplacer les boucles utilisées en programmation impérative, parfois de façon plus claire. C'est donc important de bien comprendre ce concept. Si vous avez du mal avec ce chapitre, vous pouvez aussi essayer de lire le tutoriel de bluestorm sur la récursivité. Les langages utilisés sont PHP et OCaml (vous n'aurez pas de mal à lire le code, car la syntaxe d'ocaml est assez proche de celle utilisée en Haskell).