Aller au menu - Aller au contenu

Icône Récursivité

Avatar
Par Avatar gnomnain
Mise à jour : 01/08/2010
Creative Commons BY-SA
449 visites depuis 7 jours, dont 32 sur ce chapitre classé 248/786
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.
Retour en haut
Sommaire du chapitre :
Icône du chapitre
Chapitre précédent Sommaire Chapitre suivant
Retour en haut

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 :
Code : Haskell
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 :
Code : Autre
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).
Code : Haskell
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 :
Code : Haskell
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 :
Code : Haskell
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 :
Code : Autre
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 :
Code : Autre
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 :
Code : Haskell
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.
Retour en haut

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 :
Code : Haskell
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.
Secret (cliquez pour afficher)

Code : Haskell
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.
Code : Haskell
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]).
Code : Haskell
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 ?
Secret (cliquez pour afficher)

Code : Haskell
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.
Secret (cliquez pour afficher)

Code : Haskell
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.
Code : Haskell
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 :
Code : Haskell
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.
Code : Haskell
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).
Code : Haskell
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.
Code : Haskell
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.
Code : Haskell
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.
Code : Haskell
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 :
Code : Haskell
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.
Retour en haut
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).
Chapitre précédent Sommaire Chapitre suivant
Retour en haut

Partager

Retour en haut
6 commentaires pour "Récursivité"
Note moyenne : 3.61 / 4 (33 votes)
Pseudo Commentaire
Hors ligne sebsheep # Posté le 20/09/2009 à 11:37:15
Avatar

Études : Universite Paris Sud 11

 tuto assez bien construit dans l'ensemble, mais quelque chose me surprend :
Citation
La tail-récursivité peut améliorer légèrement les performances


Légèrement ?? Transforme ta fonction pour qu'elle prenne des float en argument (pour ne pas être géné par la limite des entiers) et lance fac 1000000. Tu n'auras pas de résultat ! Tu vas saturer la pile d'appel.
Tu vas me dire que pour factorielle, ce n'est aps très important vu qu'on a infinity à partir de fac 100, mais sur une autre fonction plus grosse, le même phénomène peut se produire sur un argument plus petit.

Donc je ne suis pas d'accord avec toi, dès que l'on peut écrire une fonction de manière tail-récursive, on le fait ! Je ne sais pas si c'est toujours possible, toujours est-il que j'y suis toujours arrivé jusqu'à présent.
"Il y a deux choses infinies dans le monde : l'univers et la bêtise humaine ... mais pour l'univers j'ai un doute"
Image utilisateur
Tuto sur l'aléatoire et les probabilités.
Un aperçu de Monte Carlo
 
Hors ligne gnomnain # Posté le 20/09/2009 à 12:29:02
Blblbl !
Avatar

Avis : Très bon Groupe : Anciens

On le ferait dans un langage qui n'utilise pas l'évaluation paresseuse, comme Ocaml, mais en Haskell c'est pas forcément le plus intelligent, et il faut mieux comprendre les implications que ça a, notamment au niveau de l'évaluation paresseuse. Si tu fais ça sans faire attention, tu peux très facilement créer une fonction qui va utiliser toute la mémoire disponible en "empilant" des valeurs pas encore évaluées, au lieu d'effectuer le calcul immédiatement (n'essaye surtout pas de faire foldl (&&) True (repeat False) . De plus, tu perds la paresse de ta fonction (essaye par exemple foldl' (&&) True (repeat False) et foldr (&&) True (repeat False) : la deuxième version renvoie immédiatement False, alors que la deuxième doit parcourir toute la liste (infinie) en entier).
Image utilisateur
Haskell - Learn You a Haskell - Real World Haskell - xmonad - OCaml
Apprenez Haskell ! - #ircduzero
<colbseton> Serialk: tu cherches vraiment des liens logiques dans tout ce que je raconte ?
 
Hors ligne Mylans # Posté le 28/10/2009 à 16:46:19
Avatar

Ville : Tours
Pays : France métropolitaine
Études : Lycée Descartes - Tours

 Hello

N'y a-t-il pas un erreur au niveau du tri par fusion ?
la fonction fusion prend deux listes pour arguments, et la fonction triFusion lui donne un couple.

Code : Autre
1
2

triFusion l = let (xs,ys) = couper l in 
              fusion (triFusion xs, triFusion ys)
Hors ligne gnomnain # Posté le 28/10/2009 à 16:55:32
Blblbl !
Avatar

Avis : Très bon Groupe : Anciens

Ouais Mylans, merci pour la remarque, ça sera corrigé dans le prochain lot de changements.
Image utilisateur
Haskell - Learn You a Haskell - Real World Haskell - xmonad - OCaml
Apprenez Haskell ! - #ircduzero
<colbseton> Serialk: tu cherches vraiment des liens logiques dans tout ce que je raconte ?
 
Hors ligne spider-mario # Posté le 23/01/2010 à 22:53:52
Avatar

Avis : Très bon

Ville : Montigny-lès-cormeilles
Pays : France métropolitaine
Études : INSA Rouen

 Citation : sebsheep
Transforme ta fonction pour qu'elle prenne des float en argument (pour ne pas être géné par la limite des entiers) et lance fac 1000000

Pourquoi se soucier de la limite des entiers ?
GHC est tel que les programmes compilés avec, lorsqu'ils utilisent le type Integer, utilisent GMP pour obtenir une précision limitée uniquement par la mémoire disponible.
C'est le type Int qui est limité.

Voir tous les commentaires