Récursivité structurelle

Récursivité structurelle

Listes et arbres sont des structures de données informatiques définies récursivement : un arbre est soit une feuille (élément de base), soit la donnée d'un nœud (élément de base) et d'une liste finie de sous arbres qui sont des arbres eux-mêmes. Une liste est soit vide, soit la donnée d'un premier élément (de la liste) et de la fin de la liste qui est une liste elle-même. Listes et arbres ne sont pas les seules structures informatiques récursives, il y a les graphes, les graphes acycliques, ... D'autres structures informatiques ne sont pas récursives : les constantes, les couples, ...

Sur ces objets récursifs les algorithmes les plus naturels sont des algorithmes récursifs basés 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 fin de liste (notation Prolog), alors l'algorithme général est formé d'une disjonction entre deux cas :

  • cas de base pour [] sans appel récursif
  • cas de propagation pour [E|L] avec appel récursif sur L.


Sommaire

combinatoire des formes de récursivité structurelle

combinatoire des cas de base

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

Selon l'algorithme à mettre en place, le cas de propagation peut être :

  • cas de propagation pour [E|L]
  • cas de propagation pour [E,F|L] avec
    • appel récursif sur L
    • appel récursif sur [F|L]

(rappel : le cas de propagation est celui qui nécessite un appel récursif)

Selon l'algorithme à mettre en place, les cas de propagation peuvent être au nombre de 1, 2 ou plus et ils peuvent engendrer un appel récursif, ou deux ou plus.

conclusion

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

Exemple de base

  • 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]

  • 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]

  • 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]

  • 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]

  • 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

  • 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

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

  • 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)

  • 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

Récapitulatif des formes de récursivité structurelle
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
valeurs possibles : [], [E], [E,F], [E | L], ... valeurs possibles : [E | L], [E, F | L], L, ... valeurs possibles : L, [E | 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 ...
[E,F | 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] [E,F | L] [F | L] 2 1 1 1 vérification qu'une liste est croissante
[], [E] et [E,F] [E,F,G | L] [F,G | L] 3 1 1 1 calcul d'une suite de fibonnaci
[E] [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
[F | L] 1 1 1 1 calcul des différences successives d'une liste
[E,F] [E | L] L 1 1 1 1 donner l'avant dernier élément d'une liste
[E | L] [E | 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

Récursivité et apprentissage

La complexité cognitive de la récursivité est probablement plus importante que celle de l'itération ou de la conditionnelle. Il y a :

  • une difficulté conceptuelle plus importante : elle est sensible quand les étudiants incrédules se demandent comment on peut utiliser une chose que l'on ne connait pas encore pour définir la chose elle-même sans tomber dans un cercle vicieux,
  • une forme de pensée algorithmique plus déclarative, moins portée par le déroulement dans le temps (plus éloignée de l'algorithmique spontanée on naïve), elle autorise moins les effets de bord, les variable globales et
  • une combinatoire importante (cf. prec.).

L'enseignement de l'algorithmique commence donc habituellement par l'itération ou de la conditionnelle plutôt que par la récursivité. À noter : cela entraine une plus grande difficulté ensuite pour apprendre/découvrir la programmation récursive.

Les vertus de la récursivité sont à trouver du côté de la correction des algorithmes produits, de leurs possibles parallélisations et des optimisations rendues possibles par la diminution des utilisations d'effets de bord ; côté apprentissage l'effort de conceptualisation des algorithmes que la récursivité nécessite entraîne un meilleur apprentissage.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Récursivité structurelle de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Récursivité — La récursivité est une démarche qui fait référence à l objet de la démarche, ainsi c est le fait de décrire un processus dépendant de données en faisant appel à ce même processus sur d autres données plus «simples», de montrer une image contenant …   Wikipédia en Français

  • Algorithme récursif — Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique. Un algorithme est dit récursif s il s appelle lui même. Les premiers langages de programmation qui ont introduit la récursivité sont LISP et Algol 60 et… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”