Récursivité : Introduction
Algorithmique et programmation/Récursivité/Introduction

Une page de Wikiversité.

< Algorithmique et programmation | Récursivité

**Introduction**
Leçon : Récursivité

Chapitre 1
Retour au	Sommaire
Chap. suiv. :	Algorithmes récursifs

La récursivité c'est l'application de l'adage « Diviser pour régner » à l'algorithmique : pour résoudre un problème d'une taille donnée, on scinde ce problème en plusieurs sous-problèmes plus petits, on recommence avec chacun de ces sous-problèmes jusqu'à ce que tous les petits sous-...-sous-problèmes soient facilement résolubles.

[modifier] Premiers pas

Soyons un peu plus formels. On dit d'une définition qu'elle est récursive si elle fait appel à elle-même pour se définir. Une telle définition peut sembler se mordre la queue, ne rien pouvoir produire de concret. Il n'en sera rien si la définition est bien construite. C'est dans le domaine mathématique que l'on trouve de nombreuses définitions récursives :

Exemple : définition récursive de la factorielle

$begin{array}{l r} n!=begin{cases} 1 & mbox{si }n=0 n(n-1)! & mbox{si }n>0 end{cases} & n in N end{array}$

Cet exemple montre les deux caractéristiques principales d'une définition récursive intéressante :

Présence d'un cas particulier ne faisant pas un appel à la définition, mais donnant un résultat $n! = 1si n = 0$
Présence d'un appel récursif mais avec un paramètre plus petit $n! = n (n - 1)! si n > 0$

Utiliser une définition récursive est souvent considéré comme élégant, concis et lisible.

[modifier] Algorithme récursif

Appliquons le même schéma aux algorithmes. Si nous disposons d'un algorithme A qui d'une manière directe fait appel à lui-même, ou d'une manière indirecte appelle un autre algorithme B qui lui appelle A, alors l'algorithme A sera dit récursif. Afin d'être correct, il doit exister au moins un cas dans lequel l'appel récursif ne se fait pas, et ce cas doit se produire.

Définition : Algorithme récursif

Un algorithme est récursif quand dans l'enchaînement des instructions qui le composent, l'une de celles-ci est un appel à ce même algorithme.

Cela donne pour notre exemple de factorielle le pseudocode suivant

Nous retrouvons en ligne 4 la condition d'arrêt : aucun appel récursif n'est mis en œuvre, et en ligne 6 l'appel récursif.

[modifier] Structure de donnée récursive

Si nous appliquons un schéma récursif à la création de structures de données, nous créons une structure de données récursive. Ces structures deviennent nécessaires dès que l'on a besoin de les agrandir dynamiquement. L'exemple le plus simple est sans doute celui de la liste. On peut implémenter une liste d'objets avec une structure élémentaire comme un tableau. Mais la gestion dynamique d'un tableau peut-être difficile à maintenir. Une liste peut alors être considérée sous une forme récursive, une liste est composée de

un élément de la liste
une sous-liste d'autres éléments

Exemple

Supposons que nous disposions de la liste de personnes suivante :
Alice, Bob, Charles, Damien

Une manière de représenter cette liste serait un tableau :

Alice

Bob

Charles

Damien

(vide)

Un tableau possédant une certaine longueur, il a ici été surdimensionné (2 cases sont vides)

Une autre manière de représenter cette liste serait une liste simplement chaînée :

$Bigg(Alice, circ mapsto bigg(Bob, circ mapsto Big(Charles, circ mapsto big(Damien, circ mapsto bold{()}quad big) Big) bigg) Bigg)$

Structure de donnée récursive

Une structure de donnée S est dite récursive si l'une de ses composantes est aussi une structure de donnée S ou si l'un de ses composantes est une structure de donnée faisant appel à S.

Algorithmique et programmation/Récursivité : Algorithmes récursifs
Algorithmique et programmation/Récursivité/Algorithmes récursifs

Une page de Wikiversité.

< Algorithmique et programmation | Récursivité

Aller à : Navigation, rechercher

**Algorithmes récursifs**
Leçon : Récursivité

Chapitre 2
Chap. préc. :	Introduction
Chap. suiv. :	Structure de données récursives

On peut distinguer plusieurs catégories d'algorithmes récursifs en considérant

Le mode d'appel : direct/indirect
Le nombre de paramètres sur lesquels porte la récursion : arité
Le nombre d'appels récursifs : ordre de récursion
Le genre de retour : terminal/non terminal

Sommaire

[masquer]

[modifier] Mode d'appel

Comme nous l'avons déjà vu dans l'introduction, un algorithme récursif qui dans son corps s'appelle lui-même est dit direct. L'exemple de la factorielle est trivial. Un algorithme récursif est dit indirect s'il est défini par un ensemble de fonctions qui s'appellent en chaîne.

Algorithme récursif indirect pour déterminer la parité d'un entier

Pour construire une définition récursive de la parité, remarquons tout d'abord que 0 est un entier pair, et qu'il n'est pas impair. Ensuite remarquons que un entier n est pair (resp. impair) ssi l'entier n-1 est impair (resp. pair).

Si l'on trace Pair(3) on obtiendra

$begin{matrix} Pair(3) & leftarrow& operatorname{underline{Faux}} & searrow & uparrow & & Impair(2) & leftarrow& operatorname{underline{Faux}} & & & searrow & uparrow & & & & Pair(1) & leftarrow& operatorname{underline{Faux}} & & & & & searrow & uparrow & & & & & & Impair(0) end{matrix}$

[modifier] Arité

L'arité d'un algorithme est le nombre de paramètres d'entrée. Un algorithme récursif peut effectuer des appels récursifs en modifiant un nombre quelconque non nul de ses paramètres. Dans l'exemple de la fonction factorielle, l'algorithme prend un paramètre d'entrée et le modifie lors des appels récursifs. Dans le cas de la puissance entière (proposé en exercice), l'algorithme prend deux entrées, la base et l'exposant. Dans les appels récursifs seul l'exposant est modifié. Voici un exemple de récursion sur deux paramètres.

Algorithme récursif de calcul du PGCD de deux entiers

[modifier] Ordre de récursion

Jusqu'à présent, tous les algorithmes récursifs évoqués ne font qu'un appel récursif à la fois, c'est-à-dire que pour déterminer la valeur d'un appel, on n'a besoin que d'un appel récursif. Ces algorithmes sont dits d'ordre 1. Certains algorithmes font plusieurs appels récursifs, comme la version naïve du calcul de la suite de Fibonnaci. Celle-ci doit faire deux appels récursifs, une fois avec le paramètre n-1 et une seconde fois avec le paramètre n-2 pour calculer une valeur de retour. C'est un algorithme récursif d'ordre 2.

Algorithme récursif pour calculer le n^ième terme de la suite de Fibbonacci

[modifier] Récursion terminale

Pour déterminer si un algorithme est terminal, il faut regarder comment il génère les valeurs de retour. Si ce sont soit des constantes, soit des valeurs directement issue d'un appel récursif, sans aucune autre modification, alors l'algorithme est dit terminal. Dans le cas contraire, il sera dit non-terminal. Cette notion est importante si l'on veut déterminer une version itérative de l'algorithme concerné. Dans les exemples précédents, factorielle est non terminal car, bien que le cas d'arrêt renvoie une constante, celui de l'appel récursif quant à lui modifie la valeur renvoyée en la multipliant par n avant de lui-même renvoyer une valeur.

Algorithmique et programmation/Récursivité : Structure de données récursives
Algorithmique et programmation/Récursivité/Structure de données récursives

Une page de Wikiversité.

< Algorithmique et programmation | Récursivité

Aller à : Navigation, rechercher

**Structure de données récursives**
Leçon : Récursivité

Chapitre 3
Chap. préc. :	Algorithmes récursifs
Chap. suiv. :	Algorithmes récursifs avancés

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.

Sommaire

[masquer]

[modifier] 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 donnacute ees & 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 donnacute ees & 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 caratè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.

[modifier] Les listes chaînées

[modifier] 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, 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} creacute er_liste & mbox{cr}acutembox{e}mbox{e une liste initialement vide (i.e. Tete est nulle)} creacute er_noeud( valeur, suivant ) & mbox{initialise un nouveau noeud} ajouter_tete( liste, noeud ) & mbox{ajoute }noeudmbox{ en t}hatmbox{e}mbox{te de liste} ajouter_queue( liste, noeud ) & mbox{ajoute }noeudmbox{ en fin de liste} effacer_tete( liste ) & mbox{efface la t}hatmbox{e}mbox{te de liste} effacer_queue( liste ) & mbox{efface la queue de liste} suivant( noeud ) & mbox{renvoie le noeud suivant} end{array}$

[modifier] Chaînage double

Si dans la définition du nœud on ajoute une référence $p r e c e d e n t$ , 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_{chainage double} & = & 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}$

[modifier] 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.

[modifier] 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.

[modifier] Les arbres

[modifier] 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.

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}$

[modifier] 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 tansformé en arbre binaire.

[modifier] 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é).

Exercice : Introduction
Algorithmique et programmation/Récursivité/Exercices/Introduction

Une page de Wikiversité.

< Algorithmique et programmation | Récursivité

Aller à : Navigation, rechercher

**Introduction**
Leçon : Récursivité

Exercice 1
Chapitre du cours :	Introduction
Cet exercice est de niveau 0.

[modifier] Puissance entière d'un entier

La fonction puissance entière peut être définie ainsi : $begin{array}{l r} x^n=begin{cases} 1 & mbox{si }n=0 x.x^{(n-1)} & mbox{si }n>0 end{cases} & x,n in N end{array}$

1. Cette définition respecte-t-elle les caractéristiques d'une définition récursive intéressante ?

2. Écrivez l'algorithme de la fonction ipower(x,n) correspondante.

Masquer

Solution

1. Cette définition respecte les caractéristiques d'une définition récursive intéressante car

il y a un appel récursif avec un problème de taille plus petite ( de ipower(x,n) on appelle ipower(x,n-1)
il y a bien une condition d'arrêt : cas où n vaut 0

2. L'algorithme de la fonction power(x,n) est le suivant :

Algorithme : Puissance entière

$begin{array}{|l} operatorname{underline{fonction}} ipower(x,n) operatorname{underline{debut}} begin{array}{|l} operatorname{underline{si}} n=0 operatorname{underline{alors}} ipower leftarrow 1 operatorname{underline{sinon}} ipower leftarrow x*ipower(x,n-1) operatorname{underline{fsi}} end{array} operatorname{underline{fin}} end{array}$

Exercice : Algorithmes récursifs
Algorithmique et programmation/Récursivité/Exercices/Algorithmes récursifs

Une page de Wikiversité.

< Algorithmique et programmation | Récursivité

Aller à : Navigation, rechercher

**Algorithmes récursifs**
Leçon : Récursivité

Exercice 1
Chapitre du cours :	Algorithmes récursifs
Cet exercice est de niveau 0.

[modifier] Fibbonacci revisité

Nous avons vu un algorithme (dit naïf) qui calcule le n^ième termde la suite de Fibbonacci :

Algorithme récursif pour calculer le n^ième terme de la suite de Fibbonacci

[ Enrouler ]

1. Tracez Fibb(5). Combien cet appel génère-t-il d'appels récursifs ? Combien au maximum y a-t-il d'appels imbriqués ?

La trace correcte de Fibb(5) est

Les appels récursifs ne se partagent pas

est incorrect.

Donc un appel à Fibb(5) génère 14 appels récursifs. Le nombre maximum d'appels imbriqués est de 4.

[modifier] Remarques

D'une manière générale, quand on calcule Fibb(n), l'imbrication maximale sera n-1, et le nombre d'appels récursifs sera $2 times F_{n}-2$

[ Enrouler ]

2. L'algorithme est-il terminal ? Justifiez la réponse.

L'algorithme n'est pas terminal, car pour retourner une valeur en ligne 8 on fait deux appels récursifs dont on additionne le résultat. La ligne 8 est équivalente à

$tmp_1 leftarrow mbox{Fibb}(n-1)$

$tmp_2 leftarrow mbox{Fibb}(n-2)$

$bold{retourner} tmp_1 + tmp_2$

Algorithme récursif pour calculer le n^ième terme de la suite de Fibbonacci (version 2)

[ Enrouler ]

3. Tracez Fibb2(5). Combien cet appel génère-t-il d'appels récursifs ? Combien au maximum y a-t-il d'appels imbriqués ?

$begin{array}{lcrcl} Fibb(5,a,b) & & a=5+3=8 & & b=5 downarrow & & scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} Fibb(4,a,b) & & a=3+2=5 & & b=3 downarrow & & scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} Fibb(3,a,b) & & a=2+1=3 & & b=2 downarrow & & scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} Fibb(2,a,b) & & a=1+1=2 & & b=1 downarrow & & scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} Fibb(1,a,b) & & a=1+0=1 & & b=1 downarrow & & scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} Fibb(0,a,b) & longrightarrow & a=1 & & b=0 end{array}$

Cet appel génère 5 appels récursifs, l'imbrication maximale est de 5 aussi.

[ Enrouler ]

4. L'algorithme est-il terminal ? Justifiez la réponse.

L'algorithme est terminal car :

seul un appel récursif est fait à la fois (ligne
les données renvoyées sont

soit des constantes (lignes 4-5)
soit des valeurs issues de l'appel récursif (lignes 9-10)
Le fait des les manipuler entre-elles ne modifie pas la terminalité d'un algorithme.

[ Enrouler ]

5. Pouvez-vous tirer de la trace donnée dans la réponse 3 un algorithme itératif de Fibb2 ?

La trace est :

On remarque qu'il y a deux temps distincts.

Dans un premier temps, les appels récursifs s'enchaînent jusqu'à trouver la condition d'arrêt. C'est la partie :

$begin{array}{lcrcl} Fibb(5,a,b) downarrow Fibb(4,a,b) downarrow Fibb(3,a,b) downarrow Fibb(2,a,b) downarrow Fibb(1,a,b) downarrow Fibb(0,a,b) & longrightarrow & a=1 & & b=0 end{array}$

Dans un second temps, on remonte en effectuant toujours les mêmes opérations $a gets a+b$ et $b gets a$ , c'est la partie :

$begin{array}{rcl} a=5+3=8 & & b=5 scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} a=3+2=5 & & b=3 scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} a=2+1=3 & & b=2 scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} a=1+1=2 & & b=1 scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} a=1+0=1 & & b=1 scriptstyle{a leftarrow a+b} & uparrow & scriptstyle{bleftarrow a} a=1 & & b=0 end{array}$

Donc pour construire une version itérative de cet algorithme, il faut dans un premier temps faire l'initialisation de la condition d'arrêt, suivie de la répétition de n fois les opérations effectuées lors de la remontée. Cela donne :

Exercice : Structure de données récursives
Algorithmique et programmation/Récursivité/Exercices/Structure de données récursives

Une page de Wikiversité.

< Algorithmique et programmation | Récursivité

Aller à : Navigation, rechercher

**Structure de données récursives**
Leçon : Récursivité

Exercice 3
Chapitre du cours :	Structure de données récursives
Cet exercice est de niveau 0.

Sommaire

[masquer]

[modifier] Structure de données récursives : une structure de type dictionnaire

[modifier] Introduction

À lire absolument, avant de commencer l'exercice

[ Enrouler ]

>Mis dans une boîte déroulante par souci de clarté

Nous nous proposons ici de créer une structure de données permettant de contenir un dictionnaire, c'est-à-dire tout simplement une liste de mots. Si nous ouvrons un dictionnaire nous observons une liste^[1] telle que :

A, subst. masc. : ... définition
À, prép, : ... définition
AALÉNIEN, IENNE, adj. et subst. masc. : ... définition
AB-, préf. : ... définition
ABA, subst. masc. : ... définition
ABACA, subst. masc. : ... définition
... ainsi de suite
ZYMOTIQUE, adj. : ... définition
ZYTHUM, subst. masc. : ... définition
ZZZ, onomat. : ... définition

Dans cet exercice, nous nous limiterons uniquement aux vedettes (le mot dont la définition est donnée à la suite, une entrée du dictionnaire), sans conserver ni leurs genres, ni leurs définitions, ni leur casse (tous les mots seront écris en minuscules). Un tel lexique pourra être tiré du dictionnaire mis à disposition par le CNAMCNAM. Il comprend 251307 mots différents (~2.6Mo, ce qui fait une moyenne 9.8 caractères par mot).

Un tel lexique peut être stocké dans un tableau à 251307 entrées (une par mot) ou dans une liste chaînée de mots. Mais en y regardant de plus près, on remarque que des mots consécutifs dans le lexique trié ont souvent un préfixe commun :

INAPPARENT
INAPPÉTENCE
INAPPLICABLE
INAPPLICATION
INAPPLIQUÉ
INAPPRÉCIABLE
INAPPRÉCIÉ
INAPPRÊTÉ
INAPPRIVOISABLE
INAPPRIVOISÉ
INAPPROCHABLE

Il est tentant de factoriser les préfixe INAPP sur toute cette liste :

INAPP
- ARENT
- ÉTENCE
- LICABLE
- LICATION
- LIQUÉ
- RÉCIABLE
- RÉCIÉ
- RÊTÉ
- RIVOISABLE
- RIVOISÉ
- ROCHABLE

On peut réitérer le procédé dans la sous-liste

- LICABLE
- LICATION
- LIQUÉ

pour la transformer en

- LI
  - CABLE
  - CATION
  - QUÉ

Si on poursuit à plus soif on obtient à partir de la première liste des INAPP

INAPP
- ARENT
- ÉTENCE
- LI
  - CA
    - BLE
    - TION
  - QUÉ
- RÉ
  - CI
    - ABLE
    - É
- RÊTÉ
- RIVOISA
  - BLE
  - SÉ
- ROCHABLE

On reconnaît là la naissance d'une structure arborescente. Mais il subsiste un petit problème, celui d'un mot entièrement contenu dans un autre. Considérons la liste

BAL
BALS
BALLE
BALLES

La construction nous conduit à

BAL
- S
- LE
  - S

Pour simplifier les choses, nous ajoutons à la fin de chaque mot un marqueur de fin de mot qui sera noté $ε$ , celà nous conduit à quelque chose comme :

Récursivité : Introduction Algorithmique et programmation/Récursivité/Introduction

Une page de Wikiversité.

[modifier] Premiers pas

[modifier] Algorithme récursif

[modifier] Structure de donnée récursive

Algorithmique et programmation/Récursivité : Algorithmes récursifs Algorithmique et programmation/Récursivité/Algorithmes récursifs

Une page de Wikiversité.

Sommaire

[modifier] Mode d'appel

[modifier] Arité

[modifier] Ordre de récursion

[modifier] Récursion terminale

Algorithmique et programmation/Récursivité : Structure de données récursives Algorithmique et programmation/Récursivité/Structure de données récursives

Une page de Wikiversité.

Sommaire

[modifier] Principe

[modifier] Les listes chaînées

[modifier] Chaînage simple

[modifier] Chaînage double

[modifier] Pile, file, etc.

[modifier] Remarques

[modifier] Les arbres

[modifier] Les arbres binaires

[modifier] Arbres n-aires

[modifier] Graphes

Exercice : Introduction Algorithmique et programmation/Récursivité/Exercices/Introduction

Une page de Wikiversité.

[modifier] Puissance entière d'un entier

Exercice : Algorithmes récursifs Algorithmique et programmation/Récursivité/Exercices/Algorithmes récursifs

Une page de Wikiversité.

[modifier] Fibbonacci revisité

[modifier] Remarques

Exercice : Structure de données récursives Algorithmique et programmation/Récursivité/Exercices/Structure de données récursives

Une page de Wikiversité.

Sommaire

[modifier] Structure de données récursives : une structure de type dictionnaire

[modifier] Introduction

[modifier] Arbre n-aire

[modifier] Transformer un arbre n-aire en arbre binaire

[modifier] Question de point de vue

[modifier] Arbre binaire

[modifier] Le dictionnaire sous forme arbre binaire

[modifier] Notes

Récursivité : Introduction
Algorithmique et programmation/Récursivité/Introduction

Algorithmique et programmation/Récursivité : Algorithmes récursifs
Algorithmique et programmation/Récursivité/Algorithmes récursifs

Algorithmique et programmation/Récursivité : Structure de données récursives
Algorithmique et programmation/Récursivité/Structure de données récursives

Exercice : Introduction
Algorithmique et programmation/Récursivité/Exercices/Introduction

Exercice : Algorithmes récursifs
Algorithmique et programmation/Récursivité/Exercices/Algorithmes récursifs

Exercice : Structure de données récursives
Algorithmique et programmation/Récursivité/Exercices/Structure de données récursives