Récursivité structurelle
Les structures récursives sont des objets mathématiques ou informatiques (on dit aussi des structures de données) qui ont la particularité d'être définis à partir de leurs constituants qui sont eux-mêmes des structures de même type. Les plus populaires de ces structures récursives sont les listes et les arbres, mais il y en a de nombreuses autres, comme les termes, les arbres binaires, les piles, les files, les quadtrees, les octrees, les graphes, les graphes orientés, les graphes acycliques, etc.
Introduction[modifier]
Les listes et les arbres sont des exemples paradigmatiques de structures de données informatiques définies récursivement. Ainsi
- un arbre est soit une feuille (élément de base), soit un couple formé d'un nœud (élément de base) et d'une liste finie d'arbres,
- une liste est soit la liste vide, soit un couple formé d'un élément et d'une liste. Dans la nouvelle liste ainsi définie, le premier élément du couple est la tête de la liste et le second élément du couple est une sous-liste de la liste définie qui est appelée la queue de la liste.
Sur ces structures récursives les algorithmes sont naturellement définis récursivement et s'appuient sur la récursivité structurelle des objets qu'ils manipulent.
Par exemple, notons [] la liste vide , [E | L] la liste ayant E comme premier élément et L comme queue de liste (notation Prolog), alors un algorithme général a deux cas :
- cas de base pour [] sans appel récursif
- cas de propagation pour [E | L] avec appel récursif sur L.
Combinatoire des formes de récursivité structurelle[modifier]
Combinatoire des cas de base[modifier]
Selon l'algorithme à mettre en place, le cas de base peut être :
- cas de base pour []
- cas de base pour [E]
- cas de base pour [E,F]
- cas de base pour [E|L]
(rappel : le cas de base est celui qui ne nécessite pas d'appel récursif)
Selon l'algorithme à mettre en place, les cas de base peuvent être au nombre de 1, 2 ou plus.
Combinatoire des cas de propagation[modifier]
Selon l'algorithme à mettre en place, le(s) cas de propagation peu(ven)t être :
- cas de propagation pour [E|L]
- cas de propagation pour [E,F|L] (ou plus) avec
- appel récursif sur L
- appel récursif sur [F|L]
- la propagation peut se dérouler
- lors d'une phase d'analyse
- lors d'une phase de synthèse
- double (rare) : lors d'une phase d'analyse puis lors d'une phase de synthèse
- les cas de propagation peuvent être au nombre de 1, 2 ou plus
- les cas de propagations peuvent engendrer un appel récursif, ou deux ou plus.
(rappel : le cas de propagation est celui qui nécessite un appel récursif)
Conclusion[modifier]
Assez naturellement, on peut dénombrer un trentaine de formes de récursivité structurelle usuelles où varient :
- la forme des cas de base
- la forme des cas de propagation
- la forme de(s) appel(s) récursif(s)
- le nombre de cas de base nécessaires à la réalisation d'un algorithme spécifique
- le nombre de cas de propagation nécessaires à la réalisation d'un algorithme spécifique
- le nombre d'appels récursifs nécessaires à la réalisation d'un algorithme spécifique
- le nombre d'éléments sur lesquels est définie une analyse récursive structurelle
Exemples[modifier]
Exemple de base[modifier]
- cas de base pour []
- cas de propagation pour [E|L] avec appel récursif sur L.
exemple (en Prolog) :
listeDeZero([]).
listeDeZero([0|L]) :- listeDeZero(L).
Exemple avec cas de base [E], et propagation [E,F|L][modifier]
- cas de base pour [E]
- cas de propagation pour [E,F|L] avec appel récursif sur L.
exemple (en Prolog) :
listeDeLongueurImpaire([E]).
listeDeLongueurImpaire([E,F|L]) :- listeDeLongueurImpaire(L).
Exemple avec cas de base [E,F][modifier]
- cas de base pour [E,F]
- cas de propagation pour [E|L] avec appel récursif sur L.
exemple (en Prolog) :
avantDernierElement([E,F],E).
avantDernierElement([E|L],R) :- avantDernierElement(L,R).
Exemple avec cas de base [E|L][modifier]
- cas de base pour [E|L]
- cas de propagation pour [E|L] avec appel récursif sur L.
exemple (en Prolog) :
contientElement([E|L],E).
contientElement([E|L],E) :- contientElement(L,E).
Exemple avec 2 cas de base, un cas de propagation [E,F|L] et un appel récursif sur [F|L][modifier]
- cas de base pour [], [E]
- cas de propagation pour [E,F|L] avec appel récursif sur [F|L].
exemple (en Prolog) :
listeCroissante([]).
listeCroissante([E]).
listeCroissante([E,F|L]) :- E<F, listeCroissante([F|L]).
Exemple avec 2 cas de propagation[modifier]
- cas de base pour [E]
- 2 cas de propagation pour [E|L] avec appel récursif sur L.
exemple (en Prolog) :
minimumListe([E],E).
minimumListe([E|L],E) :- minimumL(L,F), E<=F.
minimumListe([E|L],F) :- minimumL(L,F), E>F.
Exemple de propagation avec 2 appels récursifs[modifier]
Les exemples de propagation avec 2 appels récursifs ne sont pas courants avec des listes, ils concernent des algorithmes ayant une stratégie particulière, par exemple : "dichotomie". Pour les arbres binaires, c'est l'inverse, les algorithmes ayant une propagation avec un seul appel récursifs ne sont pas courants, on en trouve pour des arbres particuliers, par exemple les arbres "triés", le cas le plus général -sur les arbres binaires- c'est une propagation avec 2 appels récursifs.
Cependant, voila donc un exemple sur les listes avec propagation basée sur 2 appels récursifs
- cas de base pour []
- cas de propagation avec 2 appels récursifs.
exemple (en Prolog) :
triParInterclassement([],[]).
triParInterclassement(L,R) :- coupeEnDeux(L,L1,L2), triParInterclassement(L1,R1), triParInterclassement(L2,R2), interclassementListesTriées(R1,R2,R)
Exemple de récursivité sur 2 éléments[modifier]
- cas de base pour []
- cas de propagation pour [E|L] avec appel récursif sur L sur 2 éléments.
exemple (en Prolog) :
interclassementListesTriées([],L,L).
interclassementListesTriées([E|L],[],[E|L]).
interclassementListesTriées([E|L],[F|M],[E|R]) :- E<=F, interclassementListesTriées(L,[F|M],R).
interclassementListesTriées([E|L],[F|M],[F|R]) :- E>F, interclassementListesTriées([E|L],M,R).
Autres exemples (combinaisons différentes)[modifier]
- cas de base pour []
- cas de propagation pour [E,F|L] avec appel récursif sur L
exemple (en Prolog) :
listeDeLongueurPaire([]).
listeDeLongueurPaire([E,F|L]) :- listeDeLongueurPaire(L).
- cas de base pour [E]
- cas de propagation pour [E,F|L] avec appel récursif sur [F|L].
exemple (en Prolog) :
listeDesDifférencesSuccessives([E],[]).
listeDesDifférencesSuccessives([E,F|L],[D|R]) :- D is F-E, listeDesDifférencesSuccessives([F|L],R).
- cas de base pour [E,F]
- cas de propagation pour [E,F,G|L] avec appel récursif sur [F,G|L].
exemple (en Prolog) :
fibonacci([]).
fibonacci([1]).
fibonacci([1,1]).
fibonacci([E,F,G|L]):-fibonacci([F,G|L]), E is F+G.
Récapitulatif[modifier]
| Forme(s) de(s) cas de base | Forme(s) de(s) propag. | Forme(s) de(s) appel(s) récursif(s) | Nbre de cas de base | Nbre de cas de prop. | Nbre d'appels réc. | Nbre d'analyses réc. | Exemple |
|---|---|---|---|---|---|---|---|
| L], ... | L], [E, F | L], L, ... | L], ... | valeurs possibles : 1, 2, plus, ... | valeurs possibles : 1, 2, plus, ... | valeurs possibles : 1, 2, plus ... | valeurs possibles : 1, 2, plus ... | |
| Attention ! toutes les combinaisons ne sont pas forcément raisonnables | |||||||
| [] | [E | L] | L | 1 | 1 | 1 | 1 | vérifier qu'une liste ne comporte que des zéros |
| 2 | 1 | 1 | vérifier qu'une liste comporte des zéros ou des uns | ||||
| 2 | interclasser deux listes triées | ||||||
| plus | 1 | 1 | vérifier qu'une liste comporte des zéros ou des uns ou des deux ou ... | ||||
| L] | L | 1 | 1 | 1 | 1 | vérifier qu'une liste est de longueur paire | |
| L | L | 1 | 1 | 2 | 1 | tri par interclassement d'une liste | |
| [] et [E] | L] | L] | 2 | 1 | 1 | 1 | vérification qu'une liste est croissante |
| [], [E] et [E,F] | L] | L] | 3 | 1 | 1 | 1 | calcul d'une suite de fibonacci |
| [E] | L] | L | 1 | 2 | 1 | 1 | recherche du minimum d'une liste |
| [E,F | L] | L | 1 | 1 | 1 | 1 | vérifier qu'une liste est de longueur impaire | |
| L] | 1 | 1 | 1 | 1 | calcul des différences successives d'une liste | ||
| [E,F] | L] | L | 1 | 1 | 1 | 1 | donner l'avant dernier élément d'une liste |
| L] | L] | L | 1 | 1 | 1 | 1 | recherche d'un élément dans une liste |
| Forme(s) de(s) cas de base | Forme(s) de(s) propag. | Forme(s) de(s) appel(s) récursif(s) | Nbre de cas de base | Nbre de cas de prop. | Nbre d'appels réc. | Nbre d'analyses réc. | Exemple |
Voir aussi[modifier]
Erreur Lua dans Module:Catégorisation_badges à la ligne 170 : attempt to index field 'wikibase' (a nil value).Erreur Lua dans Module:Suivi_des_biographies à la ligne 189 : attempt to index field 'wikibase' (a nil value).
Cet Article wiki "Récursivité structurelle" est issu de Wikipedia. La liste de ses auteurs peut être visible dans ses historiques.
