programmation en C "Chapitre 7 : Récursivité"

Chapitre 7 : Récursivité.


6.1 Introduction
6.2 Fonctions récursives
6.3 Récursif et itératif
6.4 Analyse de documents
6.5 Exercices
6.1 Introduction
Au cours des chapitres précédents, nous avons eu l'occasion d'utiliser des fonctions, que ce soit pour éviter de recopier plusieurs fois le même code, ou pour découper le code en parties plus simples. Dans ce chapitre, nous allons voir une autre utilisation des fonctions, qui en fait un outil très puissant pour écrire des algorithmes. Cette utilisation est ce que l'on appelle la récursivité.
La récursivité est un principe assez général, qui ne se limite pas au C, ni même aux langages de programmation. Ce principe décrit la propriété de concepts ou d'objets qui se définissent à partir d'eux-mêmes.
On pourrait penser qu'un objet qui est défini à partir de lui-même n'a pas de sens : comment comprendre le sens d'un mot, si sa définition utilise ce mot ? Pour comprendre la définition du mot, ne faudrait-il pas déjà le connaître ? Nous allons voir qu'une telle définition, si l'on prend quelques précautions, peut au contraire être très claire, souvent plus claire qu'une définition ne faisant pas appel au mot lui-même.
Prenons un exemple de définition récursive d'un objet :
Une poupée russe est un objet en forme de personnage, qui contient souvent une poupée russe semblable, mais plus petite.
Pour décrire ce qu'est une poupée russe, on a bien utilisé le nom de l'objet lui-même. Cette définition est pourtant très claire, même pour quelqu'un qui n'a jamais vu un tel objet.
Les poupées russes sont très loin d'être les seuls objets pour lesquels une définition récursive a un sens. De très nombreuses notions se définissent naturellement de manière récursive, et on en trouve beaucoup en informatique. Voici un autre exemple :
Un répertoire est un élément informatique qui peut contenir des fichiers et des répertoires.
Sauriez-vous définir la notion de répertoire sans réutiliser le mot répertoire, et sans rendre la définition incomplète ? Pas facile... un répertoire est en lui-même un concept récursif.
On peut remarquer plusieurs points communs entre nos deux exemples, qui décrivent pourtant des choses très différentes : l'un est un objet du monde réel, tandis que l'autre n'est qu'une abstraction, qui n'existe que d'un point de vue logiciel.
Le premier point commun est que dans les deux cas, on décrit un objet qui peut contenir d'autres objets. C'est souvent le cas de ce que l'on décrit récursivement, mais pas toujours, nous le verrons plus tard.
Le deuxième point commun est que la définition implique qu'il est possible que l'objet ne contienne rien. Une poupée russe contient souvent une autre poupée, mais pas toujours. Un répertoire peut contenir d'autres répertoires, mais peut aussi être vide, ou ne contenir que des fichiers. On pourrait bien sûr définir une poupée russe qui contient toujours une autre poupée russe, mais on aurait alors une infinité de poupées, ce qui ne peut exister dans le monde réel et n'est qu'une idée abstraite. Ce point est commun à la plupart des définitions récursives et on la retrouvera dans toutes celles que nous définirons en langage C.
Dans le cas des fonctions, la récursivité s'exprimera tout simplement sous la forme de fonctions qui s'appellent elles-mêmes. Nous verrons comment cela fonctionne en pratique, et à quoi cela peut servir.
Nous ne verrons pas de nouvelles notions du langage C dans ce chapitre, et n'utiliserons que des éléments du langages que vous connaissez déjà. La récursivité est cependant un concept de base de la programmation, et il est important pour tout programmeur d'être à l'aise avec ce concept.
6.2 Fonctions récursives
Voyons un premier exemple de fonction récursive, et d'un programme qui l'utilise : #include void debut_fin(int nb_affichages){ printf("début %d\n", nb_affichages); if (nb_affichages > 1) debut_fin(nb_affichages - 1); printf("fin %d\n", nb_affichages);} int main(){ debut_fin(3); return 0;}
En exécutant ce programme, on obtient l'affichage suivant : début 3début 2début 1fin 1fin 2fin 3
Le programme affiche trois "début" et "fin" imbriqués les uns dans les autres. Regardons en détail les différentes étapes de l'exécution. On a mis en avant la structure imbriquée des différents appels :
Exécution de la fonction main()
Appel de debut_fin(3)
Affichage de "début 3"
(3 > 1) est vrai -> appel de debut_fin(2)
Affichage de "début 2"
(2 > 1) est vrai -> appel de debut_fin(1)
Affichage de "début 1"
(1 > 1) est faux
Affichage de "fin 1"
Affichage de "fin 2"
Affichage de "fin 3"
Retour de l'appel à main()
Dans cet exemple, on passe en paramètre à la fonction le nombre d'appels récursifs imbriqués que l'on souhaite exécuter. Ce nombre est diminué de 1 à chaque appel : pour afficher 3 fois "début" et "fin", on affiche "début", puis on appelle la fonction pour afficher 2 fois "début" et "fin", puis on afficher "fin".
Que se passerait-il si l'on n'avait pas ce paramètre, comme dans l'exemple suivant : void debut_fin(){ printf("début\n"); debut_fin(); printf("fin\n");}
Lors de son appel, la fonction debut_fin() afficherait "début", puis s'appellerait elle-même, donc afficherait début, puis s'appellerait elle-même, donc... cela n'aurait pas de fin, et à aucun moment, le mot fin ne serait affiché.
De la même manière qu'une poupée russe, pour être un objet concret, doit pouvoir ne pas toujours contenir d'autre poupée russe, une fonction récursive ne doit pas toujours se rappeler, sinon elle ne se terminera jamais. On peut ainsi définir la règle suivante :
Une fonction récursive doit toujours comporter une condition de fin des appels, pour ne pas avoir une exécution infinie.
Voyons maintenant ce qui se passe si au lieu d'avoir un seul appel, la fonction récursive se rappelle elle-même deux fois de suite : void debut_fin(int nb_affichages){ printf("début %d\n", nb_affichages); if (nb_affichages > 1) { debut_fin(nb_affichages - 1); debut_fin(nb_affichages - 1); } printf("fin %d\n", nb_affichages);}
L'affichage du programme est alors le suivant : début 3début 2début 1fin 1début 1fin 1fin 2début 2début 1fin 1début 1fin 1fin 2fin 3
En ajoutant des indentations, on voit plus nettement ce qui se passe : début 3 début 2 début 1 fin 1 début 1 fin 1 fin 2 début 2 début 1 fin 1 début 1 fin 1 fin 2fin 3
L'appel de la fonction la rappelle deux fois, et chacun de ces appels la rappelle également deux fois.
Exercice : résolvez le problème "Nombre encadré" de l'épreuve correspondant à ce chapitre.
Exercice : résolvez le problème "0 + 0 = la tête à toto" de l'épreuve.
6.3 Récursif et itératif.
6.3.1 Factorielle en itératif et récursif
Les exemples d'utilisation des fonctions récursives que nous avons vus jusqu'à présent avaient tous une nature récursive, car ils mettaient en oeuvre des éléments imbriqués les uns dans les autres. Comme nous allons le voir, il aurait tout à fait été possible de programmer ces exemples sans utiliser de fonctions récursives. De la même manière, il n'est pas nécessaire qu'un problème ait en lui-même une nature récursive, pour qu'il soit possible de le résoudre très simplement avec une fonction récursive.
Prenons par exemple le calcul de la factorielle d'un nombre, une fonction mathématique qui pour une valeur entière positive, retourne le produit de tous les entiers entre 1 et cette valeur. Pour une valeur nulle, la fonction retourne 1. Par exemple, la factorielle de 5, que l'on note "5!", vaut 1*2*3*4*5 = 120.
On peut écrire la fonction factorielle sous la forme d'une simple boucle, de la manière suivante : int factorielle(int valeur){ int total = 1; int cur_valeur; for (cur_valeur = 1; cur_valeur <= valeur; cur_valeur++) total *= cur_valeur; return total;}
Il est cependant possible de donner une définition récursive de la fonction factorielle :
La factorielle d'un nombre N vaut 1 si N est égal à 0, et N multiplié par la factorielle de N - 1 sinon.
Cette définition est parfaitement équivalente à la précédente, et peut se traduire en code par une fonction récursive : int factorielle(int valeur){ if (valeur == 0) return 1; else return valeur * factorielle(valeur - 1);}
On peut remarquer que le code de cette deuxième version est plus simple que la version avec une boucle, et qu'il peut se lire quasiment comme une définition.
La première version, qui utilise une boucle, est ce que l'on appelle une implémentation itérative de la fonction factorielle : on effectue un certain nombre d'itérations d'une boucle. La deuxième version s'appelle tout simplement l'implémentation récursive.
6.3.2 Avantages et inconvénients
Une grande partie des problèmes peut se résoudre avec une implémentation récursive, comme avec une implémentation itérative. L'une ou l'autre peut paraître plus ou moins naturelle suivant le problème, ou suivant les habitudes du programmeur. Avec un peu d'habitude, utiliser l'implémentation récursive permet souvent d'avoir un programme plus simple, plus facile à comprendre, donc à débugger.
L'implémentation récursive a cependant deux principaux inconvénients, qui peuvent être gênants dans certains cas :
Un appel de fonction prend plus de temps qu'une simple itération de boucle.
Un appel de fonction utilise une petite quantité de mémoire.
Le premier inconvénient fait que des programmes implémentés avec une fonction récursive seront souvent légèrement plus lents que leurs équivalents itératifs. Si le moindre gain de vitesse pour cette partie de votre programme est important, il peut donc être préférable d'utiliser une implémentation itérative. Dans le cas contraire, la perte de performances peut être largement compensée par le gain en clarté du code, donc en réduction de risques de laisser des bugs.
Le deuxième inconvénient peut être très gênant si le nombre d'appels imbriqués est très important. Chaque appel de fonction imbriqué utilise une certaine quantité de mémoire, plus ou moins importante selon le nombre de paramètres et de variables de votre fonction. Cette mémoire est libérée dès que l'exécution de la fonction se termine, mais dans le cas d'une fonction récursive, cette quantité de mémoire est multipliée par le nombre d'appels imbriqués à un moment donné. Si ce nombre d'appels imbriqués peut atteindre des centaines de milliers, voire des millions, on peut facilement atteindre des méga-octets de mémoire, pour un calcul qui ne prendrait aucune mémoire avec une fonction itérative.
Dans le cas du calcul de la factorielle, le nombre d'appels récursifs imbriqués est égal à la valeur passée en paramètre. En pratique, on ne peut pas dépasser 12, car 13! vaut plus de 4 milliards, donc que le résultat du calcul ne peut être stocké dans un entier 32 bits. La mémoire utilisée est alors négligeable.
Dans certains cas, le compilateur est capable d'éviter de lui-même ces deux inconvénients, en transformant automatiquement votre fonction récursive en un programme itératif. Ceci reste cependant assez rare, et il ne faut donc pas trop compter dessus avec les compilateurs actuels.
6.3.3 Itératif vers récursif : simple boucle
Un programme itératif se base sur des boucles pour traiter un certain nombre d'éléments. Un programme itératif simple peut donc ressembler à l'exemple suivant, qui affiche un certain nombre de fois un caractère : void affiche_ligne(int nb_affichages, char caractere){ int affichages ; for (affichages = 0; affichages < nb_affichages; affichages++) printf("%c", caractere); printf("\n");}
Pour écrire une version récursive de ce programme, on commence par se demander dans quel cas la boucle n'est pas du tout utilisée. En l'occurence, il s'agit du cas où le paramètre nb_affichages vaut 0, donc qu'on ne fait qu'afficher le retour à la ligne. On peut alors commencer à écrire une fonction qui gère ce cas : void affiche_ligne(int nb_affichages, char caractere){ if (nb_affichages == 0) printf("\n");}
Reste à gérer le cas où il y a des choses à afficher. Le principe de la fonction récursive est qu'elle s'occupe d'une seule étape, et laisse les étapes suivantes pour les appels imbriqués. Dans le cas où il y a des caractères à afficher, la fonction doit donc afficher un caractère, puis se rappeler, avec comme paramètre le nombre de caractères restant à afficher. Il s'agit de la valeur qu'on lui a transmise, diminuée de 1 : void affiche_ligne(int nb_affichages, char caractere){ if (nb_affichages == 0) printf("\n"); else { printf("%c", caractere); affiche_ligne(nb_affichages-1, caractere); }}
Cette fonction réalise exactement la même chose que la version itérative. On peut ainsi dire en français : pour afficher une ligne de N caractères, il faut afficher un caractère, puis afficher une ligne de N-1 caractères.
Exercice : résolvez le problème "Entre deux" de l'épreuve, en utilisant une fonction récursive.
6.3.3 Itératif vers récursif : double boucle
Voyons maintenant comment implémenter en récursif, un programme itératif contenant deux boucles imbriquées : void affiche_rectangle(int nb_lignes, int nb_colonnes, char caractere){ int ligne, colonne; for (ligne = 0; ligne < nb_lignes; ligne++) { for (colonne = 0; colonne < nb_colonnes; colonne++) printf("%c", caractere); printf("\n"); }}
On commence par utiliser le principe de transformation d'une simple boucle, en l'appliquant sur la boucle principale. On obtient alors : void affiche_rectangle(int nb_lignes, int nb_colonnes, char caractere){ int colonne; if (nb_lignes == 0) return; for (colonne = 0; colonne < nb_colonnes; colonne++) printf("%c", caractere); printf("\n"); affiche_rectangle(nb_lignes - 1, nb_colonnes, caractere);}
On peut alors faire comme si ce programme était un simple programme itératif, et appliquer le principe sur la boucle qu'il contient. Pour que le programme ne fasse aucune boucle, il faut que le nombre de colonnes soit égal à 0. Sinon, on affiche un caractère, puis on rappelle la fonction. Il faut cependant que le rappel de la fonction n'exécute que le contenu de cette boucle, en n'affichant qu'une ligne. On a donc le programme suivant : void affiche_rectangle(int nb_lignes, int nb_colonnes, char caractere){ if (nb_lignes == 0) return; if (nb_colonnes == 0) printf("\n"); else { printf("%c", caractere); affiche_rectangle(1, nb_colonnes - 1, caractere); affiche_rectangle(nb_lignes - 1, nb_colonnes, caractere); }}
On pourrait exprimer en français qu'afficher un rectangle de N lignes M caractères, c'est afficher le premier caractère de la première ligne, puis afficher une ligne de M - 1 caractères, puis afficher N - 1 lignes de M caractères.
Bien sûr, les programmes itératifs sont rarement aussi simples, et en faire des versions récursives peut devenir plus difficile. On a cependant très rarement besoin de le faire, car avec un peu d'habitude, on peut penser directement à la version récursive du problème. Une fois que l'on a l'habitude de manipuler les versions itératives et récursives, on peut choisir plus facilement celle qui est la mieux adaptée à chaque problème.
6.3.4 Exercice
Résolvez le problème "Retournement de chaîne", dans l'épreuve correspondant à ce chapitre.
6.4 Analyse de documents
De nombreux langages ont une structure récursive. Le langage C lui-même est composé de fonctions qui contiennent des blocs d'instructions entre accolades, qui peuvent eux-mêmes contenir des blocs d'instructions, etc. Une simple expression mathématique a une nature récursive, en particulier lorsque l'on utilise des expressions parenthésées, qui peuvent elles-mêmes contenir d'autres expressions parenthésées, etc. D'autres langages, comme par exemple le XML, font également un usage important de la récursivité.
Les documents écrits dans ces langages étant récursifs par nature, utiliser des fonctions récursives pour les analyser semble tout naturel. L'analyse de documents dans des langages évolués est quelque-chose d'assez complexe, qui demande des algorithmes évolués, mais dans les cas les plus simples, de simples fonctions récursives peuvent se révéler très pratiques.
Prenons par exemple le cas de l'utilisation de parenthèses dans une expression mathématique. L'expression "(a * (b + (a - v)))" est englobée dans des parenthèses, à l'intérieur desquelles se trouvent d'autres expressions parenthésées. On peut par exemple utiliser une fonction récursive pour déterminer si une telle expression est bien parenthésée, c'est-à-dire qu'à toute parenthèse ouvrante correspond une parenthèse fermante, placée correctement.
Le programme suivant vérifie si une expression contenant uniquement des parenthèses, est correctement parenthésée. #include char bien_parenthesee(){ char car_lu; scanf("%c", &car_lu); while (car_lu == '(') { if (bien_parenthesee() != ')') return '\0'; scanf("%c", &car_lu); } return car_lu;} int main(){ char car_fin = bien_parenthesee(); if ((car_fin == '\n') (car_fin == '\r')) printf("yes\n"); else printf("no\n"); return 0;}
La fonction bien_parenthesee s'appelle récursivement à chaque fois qu'elle rencontre une parenthèse ouvrante. Lorsqu'un caractère différent est rencontré, elle s'arrête et retourne le caractère à l'appelant. Lorsque l'appelant est la fonction elle-même, celle-ci vérifie que le caractère retourné est bien le ')' qui ferme la parenthèse qu'elle a ouverte.
Pour bien comprendre son fonctionnement, n'hésitez pas à regarder à la main ce que donnerait son exécution pour une chaîne comme "(())()".
Lorsque l'on exécute ce programme sur une expression, on effectue un appel récursif à chaque fois que l'on entre dans une nouvelle paire de parenthèses imbriquées. Les appels récursifs imbriqués suivent exactement la structure des parenthèses imbriquées de l'expression. Pour l'exemple "(())()", les appels de la fonction suivent la forme suivante : - appel de bien_parenthesee() //traite l'ensemble de l'expression : "(())()" - appel de bien_parenthesee() //traite la première partie de l'expression : "(())" - appel de bien_parenthesee() //traite la sous-expression de la première partie : "()" - retourne ')' - retourne ')' - appel de bien_parenthesee() //traite la deuxième partie de l'expression : "()" - retourne ')'- retourne '\n'
A chaque fois qu'un '(' est rencontré, un appel récursif est effectué, et l'on augmente le niveau d'imbrication. Lorsqu'un caractère ')' (ou autre) est rencontré, on sort de la fonction actuelle, donc diminue le niveau d'imbrication.
Exercice : résolvez le problème "Expressions parenthésées, crochetées, ..." de l'épreuve correspondant à ce chapitre.
Exercice : résolvez le problème "Indenter son code" de l'épreuve correspondant à ce chapitre.

Commentaires