Récursivité dans l'algorithmique et la programmation/Structure de données récursives

Début de la boite de navigation du chapitre

La structure de donnée récursive est monnaie courante dans l'informatique de tous les jours; elle apparaît dès que l’on parle de liste, file, arbre, graphe, ... Peu de langages de programmation n'en permettent pas l'utilisation, que ce soit explicitement par l'intermédiaire de pointeurs, ou implicitement par des références. Nous nous bornerons ici à en décrire succinctement le principe, et à en présenter les plus courantes.

fin de la boite de navigation du chapitre

Principe

La plupart des langages permettent de créer de nouveaux types de données qui sont la réunion de plusieurs autres types de données (struct en C/C++, record en Pascal, classes pour les langages objets, ...). Rendre un type auto référant, consiste simplement à créer un type T et à le munir d'au moins un membre dont le type sera T. Évidemment, tout comme pour les algorithmes, le cas où un type T contient un membre de type S, et que ce dernier contient un membre de type T est englobé par le définition. La représentation classique d'une instance de ce type est formalisée par

${\begin{array}{ll}{\begin{array}{|l|r|}\hline donn{\acute {e}}es&\ \\\hline \end{array}}&\!\!\!\!\!\!\!\!\longrightarrow \\\end{array}}$

La partie données est l'information maintenue par ce type, la case blanche représente une référence vers ce même type et la flèche indique que cette référence est utilisée et pointe vers l'instance concernée. Si la référence ne pointe pas vers une instance alors cela est formalisé ainsi :

${\begin{array}{ll}{\begin{array}{|l|r|}\hline donn{\acute {e}}es&\bullet \\\hline \end{array}}&\ \\\end{array}}$

Une telle instance indique une terminaison (fin de la liste, feuille d'un arbre)

${\begin{array}{ll}{\begin{array}{|lcl|}\hline &Chat&\ \\\hline \quad \bullet \quad \vline &\bullet &\vline \quad \quad \\\hline \end{array}}&\\&\!\!\!\!\!\!\!\!\!\searrow \\&{\begin{array}{|lcl|}\hline &Chien&\ \\\hline \quad \bullet \quad \vline &\bullet &\vline \quad \bullet \quad \\\hline \end{array}}\\\end{array}}$

Représente une instance d'un type agrégeant une chaîne de caractères, trois références. Cette instance contient contient la chaîne de caractères Chat. Les deux premières références ne sont pas utilisées, on dit que leur valeur est nulle, elles ne pointent nulle part. La dernière référence pointe vers une instance du même type contenant la chaîne de caractère Chien. L'ordre des références est en général important.

Les listes chaînées

Chaînage simple

Les listes simplement chaînées permettent de représenter des listes d'éléments quelconques.

${\begin{array}{l}{\begin{array}{ll|l}\operatorname {\underline {type}} \ noeud&=&\operatorname {\underline {structure}} \\&&\quad m_{1}\ :\ type_{1}\\&&\quad \cdots \\&&\quad m_{n}\ :\ type_{n}\\&&\quad suivant\ :\ noeud\\&&\operatorname {\underline {fstructure}} \\\end{array}}\\\\{\begin{array}{ll|l}\operatorname {\underline {type}} \ liste\ \ &=&\operatorname {\underline {structure}} \\&&\quad tete\ :\ noeud\\&&\operatorname {\underline {fstructure}} \\\end{array}}\\\end{array}}$

Une instance particulière appelée tête de liste est une référence sur le premier élément de la liste. La liste d'entiers (5, 2, 17, 8) pourrait être représentée ainsi :

$\operatorname {Tete} \longrightarrow {\begin{array}{ll}{\begin{array}{|l|r|}\hline 5&\ \\\hline \end{array}}&\!\!\!\!\!\!\!\!\longrightarrow \\\end{array}}{\begin{array}{ll}{\begin{array}{|l|r|}\hline 2&\ \\\hline \end{array}}&\!\!\!\!\!\!\!\!\longrightarrow \\\end{array}}{\begin{array}{ll}{\begin{array}{|l|r|}\hline 17&\ \\\hline \end{array}}&\!\!\!\!\!\!\!\!\longrightarrow \\\end{array}}{\begin{array}{ll}{\begin{array}{|l|r|}\hline 8&\bullet \\\hline \end{array}}&\ \\\end{array}}$

On dispose entre autres des fonctions d'accès suivantes pour écrire nos algorithmes : ${\begin{array}{ll}cre{\acute {e}}r\_liste&{\mbox{cr}}{\acute {\mbox{e}}}{\mbox{e une liste initialement vide (i.e. Tete est nulle)}}\\cre{\acute {e}}r\_noeud(\ valeur,\ suivant\ )&{\mbox{initialise un nouveau noeud}}\\ajouter\_tete(\ liste,\ noeud\ )&{\mbox{ajoute }}noeud{\mbox{ en t}}{\hat {\mbox{e}}}{\mbox{te de liste}}\\ajouter\_queue(\ liste,\ noeud\ )&{\mbox{ajoute }}noeud{\mbox{ en fin de liste}}\\effacer\_tete(\ liste\ )&{\mbox{efface la t}}{\hat {\mbox{e}}}{\mbox{te de liste}}\\effacer\_queue(\ liste\ )&{\mbox{efface la queue de liste}}\\suivant(\ noeud\ )&{\mbox{renvoie le noeud suivant}}\\\end{array}}$

Chaînage double

Si dans la définition du nœud on ajoute une référence $precedent$, avec la contrainte que pour un nœud N qui n'est ni la tête ni la queue suivant(precedent(N))=precedent(suivant(N))=N, alors on obtient une liste doublement chaînée. Elle peut se parcourir aussi bien de la tête vers la queue que dans l'autre sens.

${\begin{array}{l}{\begin{array}{ll|l}\operatorname {\underline {type}} \ noeud&=&\operatorname {\underline {structure}} \\&&\quad m_{1}\ :\ type_{1}\\&&\quad \cdots \\&&\quad m_{n}\ :\ type_{n}\\&&\quad suivant\ :\ noeud\\&&\quad precedent\ :\ noeud\\&&\operatorname {\underline {fstructure}} \\\end{array}}\\\\{\begin{array}{ll|l}\operatorname {\underline {type}} \ liste_{chainagedouble}\ \ &=&\operatorname {\underline {structure}} \\&&\quad tete\ :\ noeud\\&&\operatorname {\underline {fstructure}} \\\end{array}}\\\end{array}}$

$\operatorname {Tete} \longrightarrow {\begin{array}{lll}&{\begin{array}{|l|c|r|}\hline \bullet &5&\ \\\hline \end{array}}&\!\!\!\!\!\!\!\!\longrightarrow \\\end{array}}\longleftarrow \!\!\!\!\!\!\!\!\!\!\!\!\!{\begin{array}{lll}&{\begin{array}{|l|c|r|}\hline \ &2&\ \\\hline \end{array}}&\!\!\!\!\!\!\!\!\longrightarrow \\\end{array}}\longleftarrow \!\!\!\!\!\!\!\!\!\!\!\!\!{\begin{array}{lll}&{\begin{array}{|l|c|r|}\hline \ &17&\ \\\hline \end{array}}&\!\!\!\!\!\!\!\!\longrightarrow \\\end{array}}\longleftarrow \!\!\!\!\!\!\!\!\!\!\!\!\!{\begin{array}{lll}&{\begin{array}{|l|c|r|}\hline \ &8&\bullet \\\hline \end{array}}\\\end{array}}$

Pile, file, etc.

Les piles et les files sont simplement des listes simplement ou doublement chaînées, seules leurs fonctions d'accès diffèrent. En ce qui concerne la pile, on peut uniquement empiler (ajouter en tête), et dépiler (récupération de la valeur de tête, destruction de celle-ci). Quant à la file, on peut seulement enfiler (ajouter en tête) et défiler (récupération de la valeur de queue, destruction de celui-ci). Parmi les implémentations particulières de listes, on pourra citer, les ensembles (chaque valeur est présente une et une seule fois dans la liste), les listes de hashage, les matrices creuses.

Remarques

Les listes apportent un comportement dynamique qui fait parfois défaut aux tableaux. Les tableaux de dimension supérieure à 1 peuvent avantageusement être remplacés par des listes de listes.

Les arbres

Les arbres binaires

Un arbre binaire représente une structure hiérarchique, comme un arbre généalogique. Le nœud de l'arbre est composé de deux références (tout comme un nœud de liste doublement chaînée), on les nomme souvent FG pour fils gauche et FD pour fils droit. Il faut voir ces liens comme un chemin que l’on emprunte à partir de la racine jusqu'à un nœud. La seule contrainte à propos de ce chemin est qu’il ne doit en exister qu'un à partir de la racine vers un nœud quelconque.

${\begin{array}{l}{\begin{array}{ll|l}\operatorname {\underline {type}} \ noeud&=&\operatorname {\underline {structure}} \\&&\quad m_{1}\ :\ type_{1}\\&&\quad \cdots \\&&\quad m_{n}\ :\ type_{n}\\&&\quad FG\ :\ noeud\\&&\quad FD\ :\ noeud\\&&\operatorname {\underline {fstructure}} \\\end{array}}\\\\{\begin{array}{ll|l}\operatorname {\underline {type}} \ arbre\ \ &=&\operatorname {\underline {structure}} \\&&\quad racine\ :\ noeud\\&&\operatorname {\underline {fstructure}} \\\end{array}}\\\end{array}}$

On définit des propriétés telles que le degré d'un nœud (nombre de reférences utilisées, i.e. n'ayant pas une valeur nulle), la hauteur d'un arbre (nombre maximum de descendants), le niveau d'un nœud (distance le séparant de la racine). Un nœud de degré 0 est appelé feuille, un nœud de degré supérieur à 0 est appelé nœud interne.

Début de l'exemple

Arbre binaire

${\begin{matrix}&&&&&Racine\\&&&&&\downarrow \\&&&&&{\begin{array}{|ccc|}\hline &8&\ \\\hline \ &\vline &\ \\\hline \end{array}}\\&&&&\ &&\ \\&&&\swarrow &&&&\searrow \\&&{\begin{array}{|ccc|}\hline &2&\ \\\hline \ &\vline &\ \\\hline \end{array}}&&&&&&{\begin{array}{|ccc|}\hline &17&\ \\\hline \ &\vline &\bullet \\\hline \end{array}}\\&\swarrow &&\searrow &&&&\swarrow \\{\begin{array}{|ccc|}\hline &1&\ \\\hline \bullet &\vline &\bullet \\\hline \end{array}}&&&&{\begin{array}{|ccc|}\hline &5&\ \\\hline \bullet &\vline &\bullet \\\hline \end{array}}&&{\begin{array}{|ccc|}\hline &10&\ \\\hline \bullet &\vline &\bullet \\\hline \end{array}}\\\end{matrix}}$

qui le plus souvent est simplifié en

${\begin{matrix}&&&&&Racine\\&&&&&\downarrow \\&&&&&8\\&&&&\ &&\ \\&&&\swarrow &&&&\searrow \\&&2&&&&&&17\\&\swarrow &&\searrow &&&&\swarrow \\1&&&&5&&10\\\end{matrix}}$

Fin de l'exemple

Arbres n-aires

Un arbre qui est composé de nœuds pouvant avoir au maximum n références est dit arbre n-aire. On le retrouve dans l'arborescence du disque dur, par exemple. Un arbre unaire est une liste, on dit qu’il a dégénéré en liste. Tout arbre n-aire peut être transformé en arbre binaire.

Graphes

Si l’on construit une structure avec un nombre quelconque de références, sans contraintes particulières (cycle, connexité, ...) alors on obtient un graphe. Un exemple courant de graphe est une carte routière où les villes sont les nœuds et les routes les références. Les graphes sont des outils d'une puissance extraordinaire, mais leur maîtrise est complexe (mais pas compliqué).