J'utiliserai dans cette dernière partie un langage plus adapté à la programmation récursive, nommé OCaml. Polyvalent, il est entre autres utilisé pour l'enseignement de la programmation en France, dans certaines universités, écoles d'ingénieurs ou classes préparatoires.
Les exemples n'utiliseront que peu de concepts de ce langage, vous pourrez donc les lire même si vous ne le connaissez pas. Les deux seules règles à connaître pour l'instant sont les suivantes :
- une fonction n'est pas déclarée par le mot-clé function comme en PHP, mais par le mot-clé let, qui sert aussi à déclarer les autres variables. Si la fonction est récursive, on ajoute après le let le mot-clé rec
- on n'utilise pas la forme if (...) { ... } else {... } du C ou du PHP, mais simplement if ... then ... else ...
Voici par exemple une fonction factorielle codée en OCaml :
Code : OCaml | let rec fac(n) =
if n = 0 then 1
else n * fac(n-1)
|
La définition reprend ainsi la description mathématique : « factorielle de n vaut 1 si n = 0, et n * factorielle de (n-1) sinon » . Simple, n'est-ce pas ?
Récursion terminale
On entend parfois certaines personnes affirmer « la récursion, c'est plus lent que les boucles » . Dans ce paragraphe, je vais vous expliquer ce qui a motivé cet argument, et pourquoi c'est un mauvais argument.
La pile d'appels
Prenons un exemple de fonction récursive très simple (c'est-à-dire ici "traduisible par une boucle sans aucun problème") :
Code : PHP | <?php
function rebours($n)
{
if ($n == 0) echo "partez !\n";
else {
echo "$n...\n";
rebours($n-1);
}
}
?>
|
Que fait l'interpréteur PHP, quand il doit exécuter
rebours(3) ?
Code : Autre1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| appel de rebours(3) :
3 différent de 0 -> choix du else
echo "3..."
appel de rebours(2) :
2 différent de 0 -> choix du else
echo "2..."
appel de rebours(1) :
1 différent de 0 -> choix du else
echo "1..."
appel de rebours(0) :
0 == 0 -> choix du if
echo "partez !"
rebours(0) terminé
rebours(1) terminé
rebours(2) terminé
rebours(3) terminé |
Comme on a pu le voir pour la fonction factorielle, les appels récursifs se déroulant à l'intérieur de la fonction
s'empilent :
rebours(3) appelle
rebours(2), attend que
rebours(2) se termine, puis se termine. Bien sûr,
rebours(2) aura appelé
rebours(1), qui appelle lui-même
rebours(0), qui n'appelle personne (ouf !).
Il est facile de se perdre dans tous ces appels récursifs. Eh bien l'interpréteur PHP risque de se perdre aussi ! Pour s'y retrouver, il stocke dans un endroit particulier une
pile d'appels, qui lui permet de savoir où il est dans la récursion (par exemple « tu es en train d'appeler
rebours(1), et quand tu auras fini, il faudra faire la suite de
rebours(2) » .
Ce n'est pas un concept spécifique à PHP : quasiment tous les langages de programmation utilisent une pile d'appel pendant l'exécution des programmes. Cette pile d'appels est invisible pour le programmeur (tous les appels de fonctions, même les non récursives, utilisent cette pile d'appel), et les détails précis de son fonctionnement dépendent du langage utilisé, mais elle peut avoir une importance dans certaines situations.
En effet, la fonction
rebours telle qu'elle est codée a la particularité de faire un appel pour toutes les valeurs entre
$n (ici 3) et 1. Comme la pile d'appels stocke tous les appels, on sait qu'à un moment donné de l'exécution (par exemple au moment où elle affiche "partez !"), elle devra se souvenir de l'appel actuel (
rebours(0)) mais aussi de tous les appels en cours (
rebours(1),
rebours(2), ...,
rebours($n)), c'est-à-dire de
$n+1 appels au total.
Cela signifie qu'au cours de l'exécution de notre fonction, la pile d'appels va grandir, et va occuper une taille d'au moins
$n+1 (je ne précise pas exactement de quelle manière la pile d'appels se comporte, car cela dépend du langage que vous utilisez).
En général ce n'est pas grave (qui a peur d'avoir une liste de 4 éléments cachée dans son programme ?), mais dans certains cas cela peut devenir gênant : si vous appelez
rebours(1000000) sur un ordinateur qui a
4 Ko de mémoire vive, vous aurez des problèmes ! Évidemment, de tels ordinateurs n'existent plus vraiment de nos jours, mais certains interpréteurs posent une limite sur la profondeur de cette pile, et cela provoquera alors une erreur.
De plus, cette manipulation de la pile a un certain coût au niveau du temps d'exécution (très très faible, mais sur
rebours(10000000), ça se verra sans doute). La version itérative (avec une boucle
for au lieu de la récursion) n'utilise qu'un seul appel de fonction, et n'a donc pas ce problème.
Voilà pourquoi certains programmeurs croient à tort que « la récursion est plus lente que l'itération » .
La récursion terminale
Il y a une remarque qui semble évidente à propos de "l'exécution" de notre programme : le tas de "rebours(..) terminé !", à la fin, ne sert absolument à rien ! En effet, au moment où on l'exécute, on a en réalité fini de faire tout ce que doit faire notre fonction (on a déjà affiché "partez..."). Ces lignes ne sont donc là que parce que l'interpréteur se "souvient" que les fonctions ont été appelées, et qu'il vérifie bien qu'elles ont fini de s'exécuter.
Est-il possible d'éviter cette partie inutile ? La réponse est (évidemment ?)
oui !
Pour l'éviter, l'interpréteur PHP n'aurait qu'à faire le constat suivant : dans la fonction
rebours($n), une fois qu'on a appelé la fonction
rebours($n-1), il n'y a plus rien à faire, on peut directement passer à la suite, sans vérifier ensuite que la fonction termine.
Ainsi, l'interpréteur pourrait se passer de la pile d'appels : actuellement, il l'utilise pour pouvoir exécuter
rebours($n-1) en étant sûr de pouvoir continuer ensuite l'exécution de
rebours($n). Il pourrait tout simplement supprimer
rebours($n) de la pile d'appel, et la remplacer directement par
rebours($n-1). Voici un schéma de la situation :
Code : Autre1
2
3
4
5
6
7
8
9
10
11
12
13
| appel de rebours(3) :
3 différent de 0 -> choix du else
echo "3..."
plus rien après rebours(2), on peut l'appeler directement :
2 différent de 0 -> choix du else
echo "2..."
plus rien après rebours(1), on peut l'appeler directement :
1 différent de 0 -> choix du else
echo "1..."
plus rien après rebours(0), on peut l'appeler directement :
0 == 0 -> choix du if
echo "partez !"
rebours(0) terminé |
Comme vous pouvez le voir à l'indentation du programme, la pile d'appels ne stockerait alors plus qu'un seul élément !
C'est ce qu'on appelle la
récursion terminale : quand l'appel récursif est la dernière "action" que fait la fonction, il est possible de remplacer l'appel actuel par l'appel récursif en question, sans augmenter la taille de la pile d'appel. On utilise souvent le terme anglais
tail-rec pour désigner les fonctions qui ont cette particularité.
Et en pratique ?
Cette idée est bien jolie, mais ce n'est qu'une hypothèse. Est-ce que PHP connaît vraiment la récursion terminale ?
La réponse est... non. Malheureusement, le PHP est un langage qui a quelques défauts, entre autres le fait d'ignorer totalement l'idée de récursion terminale. Des langages plus "évolués", ou faisant plus attention aux performances, comme OCaml, mettent en oeuvre cette stratégie. La plupart des compilateurs C (quand on active les optimisations) l'appliquent aussi à leurs fonctions, elle marche donc sûrement dans vos programmes C.
Quand vous utilisez des langages qui supportent la tail-récursion, la fonction récursive décrite ici aura
exactement les mêmes performances que la version itérative, avec une boucle (et inversement, la version itérative ira aussi vite que la fonction récursive
). Si vous utilisez un langage compilé (qui produit le code assembleur correspondant au programme, au lieu de l'exécuter directement), vous pourrez d'ailleurs sans doute vérifier que le code machine produit par le compilateur est le même (ou quasiment) pour les deux programmes.
Obtenir des fonctions tail-rec
Les fonctions
tail-rec sont donc très pratiques, mais toutes les fonctions récursives ne sont pas
tail-rec. Ainsi, à part
rebours, aucun des exemples que j'ai utilisés jusqu'à présent n'est naturellement
tail-rec. Est-ce un vrai problème ? Nous allons voir que dans certains cas, il est possible de
transformer la fonction récursive en une fonction
tail-rec.
Considérons par exemple la fonction factorielle :
Code : OCaml | let rec fac(n) =
if n = 0 then 1
else n * fac(n-1)
|
Cette fonction n'est pas
tail-rec, car l'appel récursif à
fac(n-1) n'est pas la dernière chose à faire de la fonction. Il est sur la dernière ligne, mais il faut encore récupérer le résultat, et le multiplier par
n. Si l'on essayait d'appliquer la technique de rebours (ne pas agrandir la pile d'appels), la fonction "oublierait" cette dernière opération, et renverrait un résultat complètement faux !
Il existe une méthode pour obtenir une fonction
tail-rec, qui consiste à... changer la fonction :
Code : OCaml | let rec fac(acc, n) =
if n = 0 then acc
else fac(n*acc, n-1)
|
Que fait cette fonction étrange ? Elle calcule la factorielle d'un entier :
fac(1, n) renverra bien la factorielle de
n. Voici le déroulement de l'appel de
fac(1, 3)
Code : Autre1
2
3
4
5
6
7
8
| fac(1, 3) :
3 ne vaut pas 0, donc je continue
fac(1 * 3, 2) : fac(3,2):
2 ne vaut pas 0, donc je continue
fac(3 * 2, 1) : fac(6,1) :
1 ne vaut pas 0, donc je continue
fac(6 * 1, 0) : fac(6, 0)
0 vaut 0, je renvoie acc : 6 |
Comme vous pouvez le voir, cette fonction renvoie le bon résultat. De plus, elle est
tail-rec (puisque l'appel
fac(n*acc, n-1) est vraiment la dernière chose que la fonction a besoin de faire), donc l'espace utilisé par la pile d'appels est constant.
Il reste un problème avec cette fonction : à quoi sert le 1 ? En règle générale, il est redondant (on appelle
toujours fac avec 1 comme premier argument, sauf dans le code de fac), et on a donc intérêt à définir une fonction qui ne demande pas cet argument supplémentaire :
Code : OCaml | let fac(n) =
let rec fac'(acc, n) =
if n = 0 then acc
else fac'(n*acc, n-1)
in fac'(1, n)
|
Comme vous pouvez le voir, j'ai défini une deuxième fonction
fac(n), qui contient la première définition (en OCaml, on peut déclarer une fonction à l'intérieur d'une fonction), et l'applique à l'argument demandé. Ainsi, on peut utiliser cette factorielle comme les autres (pas d'argument supplémentaire), et elle est aussi performante que la version itérative.
La transformation de la fonction factorielle que vous pouvez observer ici est l'ajout d'un
accumulateur (d'où le nom "acc"), qui sert en quelque sorte de "mémoire" entre les différents appels de la fonction, pour pouvoir renvoyer directement le résultat au moment du dernier appel. Cette méthode est relativement courante et vous la rencontrerez peut-être dans d'autres cas. Il arrive même que l'accumulateur soit utile en tant que tel, et la fonction conservera alors cet argument supplémentaire (au lieu de le "cacher" dans la définition comme ici).
Que choisir ?
Les fonctions
tail-rec sont la réponse à une question précise, « y a-t-il des différences de performances entre l'itératif et le récursif ? ». Vous savez maintenant que la réponse est « Non. » .
Est-ce que cela veut dire qu'il faut rendre toutes les fonctions tail-récursives ? La réponse est encore "non", et ce pour deux raisons.
D'une part, le
tail-rec se justifie pour des questions de
performances. Mais il faut savoir que les performances ne sont pas le seul but que doit viser le programmeur. Dans certains cas, elles ne sont même pas vraiment importantes (par exemple, quand on interagit avec l'utilisateur, qui est mille fois plus lent à choisir un bouton à la souris que n'importe quelle factorielle récursive codée avec les pieds) ; d'ailleurs, il suffit de voir le nombre de gens qui codent dans des langages "lents", comme PHP, Python ou Ruby par exemple.
Bref, un autre aspect à ne pas négliger du code est la
lisibilité. Là, l'utilisation de fonctions
tail-rec devient plus controversée. Il y a deux cas : soit la fonction est naturellement
tail-récursive (comme notre compte à rebours) et ça ne pose aucun problème, soit la fonction demande une transformation, et alors vous devez peser le pour et le contre avec soin : la transformation pose-t-elle des problèmes de lisibilité ? Si vous n'utilisez qu'une seule fois la fonction dans votre programme, privilégiez plutôt la lisibilité, et laissez-la "non
tail-rec". Si elle est souvent utilisée et constitue une part non négligeable du temps utilisé par votre programme (il existe des outils pour mesurer ça), choisissez la version
tail-rec. De toute façon, de nombreux programmeurs sont habitués à reconnaître le motif "accumulateur de fonction
tail-rec" (choisissez un nom clair pour l'argument accumulateur supplémentaire), et cela ne leur posera donc aucun problème.
D'autre part, certaines fonctions ne
peuvent pas devenir tail-récursives. Comme nous l'avons vu, une fonction est tail-récursive quand l'appel récursif est la dernière chose effectuée par la fonction. Qu'en est-il des fonctions qui font
plusieurs appels récursifs (notre exemple
max_pommes par exemple) ? Eh bien c'est simple, ces fonctions ne peuvent tout simplement pas être rendues tail-récursives : seul le dernier appel pourrait être converti en appel terminal, et tous les autres appels (dans la boucle
for de notre exemple) augmenteront la pile d'appels.
Cela pose-t-il un problème fondamental ? La réponse est non. En effet, la justification de l'optimisation
tail-rec des fonctions est d'obtenir les mêmes performances que la version itérative. Pour ce genre de fonctions (récursivité à appels multiples), il n'existe pas de version itérative équivalente qui soit aussi simple. La version récursive est donc la seule manière simple de formuler le problème, et toutes les versions itératives basées sur cet algorithme devront trouver une manière de remplacer la pile d'appels (qui stocke des informations qui nous arrangent), et leurs performances ne seront donc pas meilleures.
Conclusion
La récursivité ne produit pas fondamentalement de programmes plus lents ou plus rapides que les autres. Pour les cas particuliers des fonctions récursives reproduisant le comportement d'une simple boucle, il existe une différence (la gestion de la pile d'appel) qui est réglée simplement (en utilisant des fonctions
tail-rec). Cependant, le choix des fonctions
tail-rec ne se justifie que dans des contextes très particuliers, et vous ne devez pas vous focaliser là-dessus : dans la pratique, on écrit généralement ses fonctions de la manière la plus simple possible, pour, à la rigueur, optimiser ensuite seulement les fonctions qui demandent le plus de temps à notre programme.
De manière plus générale, le choix même d'une version récursive ou itérative d'un programme doit se faire selon plusieurs critères, mais avant tout celui de la simplicité : laquelle des versions est-elle la plus facile à comprendre ? Laquelle traduit le mieux la nature du problème ? Laquelle est la plus souple, et vous permettra d'ajouter des modifications/améliorations de l'algorithme ensuite ?
Il est nécessaire de s'habituer aux deux styles de programmation, pour pouvoir faire un choix le plus objectif ensuite : une personne qui n'aurait fait que de l'itératif aura toujours tendance à trouver la récursion "compliquée", et passera à côté d'opportunités très intéressantes, tout comme un programmeur ne faisant que de la récursion aura parfois une manière compliquée de coder ce qui se fait simplement avec une boucle.
Structures de données récursives
Jusqu'à présent, nous avons utilisé les fonctions récursives pour traiter des
problèmes que l'on pouvait qualifier de "récursifs", puisqu'ils se décomposaient en sous-problèmes semblables au problème initial. Mais la récursivité est un concept riche, qui ne se rencontre pas qu'au niveau des problèmes, mais aussi par exemple au niveau des
données : il existe des organisations de données "récursives", c'est-à-dire dont la structure se décompose en une ou plusieurs sous-structures semblables.
Définition d'une liste
L'exemple le plus simple, que je vais vous présenter ici, est la
liste. Qu'est-ce qu'une liste ? Une liste est une suite d'éléments :
[1; 2; 3; 4; 5], par exemple, est la liste des chiffres de 1 à 5. Les listes ont un nombre d'éléments qui peut être égal à 0 : la liste est alors vide, et on peut par exemple la noter
[].
Cependant, cette définition, sans doute claire pour un humain, n'est pas satisfaisante pour un ordinateur : en fait, on n'a rien expliqué du tout : qu'est-ce qu'une liste ? C'est une "suite d'éléments". Qu'est-ce qu'une suite d'éléments ? Ben... c'est une liste !
Pour pouvoir expliquer le concept de liste à un ordinateur, il faut donc une définition plus concrète. La plupart des langages utilisent une définition basée sur la représentation de ces listes dans la mémoire de l'ordinateur (une valeur, et un nombre qui indique l'adresse de l'élément suivant, etc.), mais nous allons voir qu'il existe une formulation beaucoup plus simple de cette définition. Une liste est :
- soit [], la liste vide ;
- soit un élément suivi d'une liste.
Comme vous pouvez le voir, cette définition est simple, "récursive" (elle s'utilise elle-même), et complète : la liste
[1; 2] par exemple est l'élément 1, suivi de (la liste qui est l'élément 2 suivi de la liste vide). Plus simplement, si, quand
a est un élément et
b est une liste, on note
a::b pour dire « la liste qui est constituée de l'élément a suivi de la liste b » , on peut définir la liste
[1;2] comme la liste
1::(2::[]). Cette définition est parfaitement compréhensible par l'ordinateur, et permet de représenter n'importe quelle liste.
La définition que j'ai donnée vous paraît peut-être un peu étrange. Dans ce cas, vous devriez prendre un peu de temps pour bien l'assimiler, par exemple en essayant de décomposer de petites listes selon cette définition : soit la liste vide, soit un élément (quel élément ?) suivi d'une liste (quelle liste ?).
Définition d'une liste en OCaml
Pour alléger la notation, on dira que
a::b::c est équivalent à
a::(b::c); ainsi, on n'a plus besoin de parenthèses dans
1::(2::[]), on peut écrire
1::2::[].
Comme vous l'aviez peut-être deviné, les notations que j'ai utilisées sont en fait les notations du langage OCaml :
[] désigne la liste vide, et, si
a est un élément et
b une liste, on peut écrire
a::b constituée de
a (appelé la
tête de la liste) suivi de
b (la
queue de la liste).
Voici par exemple le code OCaml qui déclare la liste [1;2;3] :
Code : OCaml | let un_deux_trois = 1 :: 2 :: 3 :: []
|
En fait, la syntaxe
[1; 2; 3] est aussi disponible, pour alléger l'écriture, mais comme vous le verrez, nous n'en avons en général pas besoin.
Quand on manipulera des listes en OCaml, on utilisera trois opérations : on commence par tester si la liste est vide (par exemple
if li = [] then ... else ..., et si elle n'est pas vide on utilise les fonctions
hd (comme "head") pour récupérer l'élément en tête de la liste, et
tl (comme "tail") pour récupérer sa queue. Il existe en fait dans le langage OCaml une méthode de manipulation bien plus jolie, mais comme le but de ce tutoriel est de présenter la récursion, et non le langage OCaml, je n'en parlerai pas.
Les langages impératifs
Dans les langages impératifs (C, Pascal, Java...), la méthode utilisée pour représenter des listes est un peu différente. Elle utilise des pointeurs (ou équivalent) pour "chaîner" entre eux les éléments de la liste. On les appelle donc souvent "listes chainées". Vous pouvez par exemple lire le tutoriel concernant
les listes chainées en C.
Quelques fonctions utilisant des listes
Comme les listes sont des structures de données naturellement récursives, les algorithmes manipulant des listes auront eux aussi tendance à être écrits récursivement.
Voyons par exemple notre premier exemple : quelle est la taille d'une liste ?
La réponse (sans coder) est évidente : la liste vide est de taille 0, et si une liste est un élément suivi d'une liste, la taille de la liste globale est la taille de la liste de queue, plus un (on compte l'élément en tête).
Voici la formulation de cette idée en OCaml :
Code : OCaml | let rec taille(liste) =
if liste = [] then 0
else 1 + taille(tl liste)
|
Voici comment le calcul se déroule sur un cas particulier (on choisit [2; 3] par exemple) :
taille(2::3::[]) = 1 + taille(3::[]) = 1 + 1 + taille([]) = 1 + 1 + 0 = 2
Voici maintenant une fonction assez amusante, qui
renverse une liste. Par exemple elle transforme la liste [1;2] en la liste [2;1]. Pour cela, on utilise une liste qui sert d'accumulateur : on enlève la tête de la liste à renverser, et on la place au fond de l'accumulateur, avant de continuer sur la queue de la liste (dont les éléments seront placés dans l'accumulateur après le premier élément, donc à l'envers) :
Code : OCaml | let renverse(liste) =
let rec rev(acc, li) =
if li = [] then acc
else rev(hd li::acc, tl li)
in rev([], liste)
|
Comme vous l'aurez sûrement remarqué, la fonction
rev est
tail-rec. Et c'est d'ailleurs un exemple de fonction "naturellement"
tail-rec, c'est-à-dire dont la formulation la plus simple utilise un accumulateur.
Idée d'exercices
Si vous souhaitez vous exercer, les listes peuvent fournir des sujets d'entraînement très intéressants.
Vous pouvez commencer par définir les listes dans votre langage de prédilection (en PHP, on pourrait par exemple utiliser un tableau vide pour la liste vide, et un tableau à deux éléments pour l'élément suivi d'une liste ; en C, un tuto existe qui présente une définition utilisant des pointeurs). Pas la peine de rechercher la structure la plus efficace au niveau des performances (clairement, les tableaux imbriqués ne sont pas très efficaces en PHP), essayez d'être simple conceptuellement.
Ensuite, vous pourrez utiliser cette structure pour écrire les fonctions de manipulation de listes.
rev, qui renverse une liste, est une bonne idée d'exercice. Voici quelques autres fonctions qui pourraient vous inspirer :
- map, qui prend en argument une liste et une fonction, et renvoie la liste des éléments auxquels on a appliqué la fonction. Par exemple map plus_un [1; 5; 7] renvoie [2; 6; 8] ;
- mem, qui prend un argument une valeur et une liste, et indique si la valeur se trouve dans la liste ;
- append, qui ajoute deux listes bout à bout : append [1;2] [3;4] renvoie [1;2;3;4] ;
- sort, qui trie une liste d'entiers (il existe de nombreux tris différents).
La récursivité
)
bluestorm
Trouvez une formation
Suggestions
Twitter
Facebook