Récursivité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est la propriété de pouvoir appliquer une même règle plusieurs fois[1],[2]. Ainsi, les cas suivants constituent des cas concrets de récursivité :

  • dans la première phrase du présent article, le mot "récursivité" pourrait être cliquable, et mener sur le présent article (mais le système de wiki détecte les liens hypertextes récursifs et les supprime) ;
  • décrire un processus dépendant de données en faisant appel à ce même processus sur d'autres données plus « simples » ;
  • montrer une image contenant des images similaires[3] ;
  • définir un concept en invoquant le même concept ;
  • écrire un algorithme qui s'invoque lui-même[4] ;
  • définir une structure à partir de ses sous-structures.

En informatique et en logique[modifier | modifier le code]

Articles détaillés : Algorithme récursif et Fonction récursive.
Un arbre binaire est une structure de données récursive.

En informatique et en logique, une fonction ou plus généralement un algorithme qui contient un ou des appel(s) à lui-même est dit récursif. Ce procédé est employé dans la conception d'algorithme basée sur le paradigme diviser pour régner. Deux fonctions peuvent s'appeler l'une l'autre, on parle alors de récursivité croisée. La définition de certaines structures de données, comme les listes, les arbres est récursive. Par exemple (voir la figure) un arbre binaire est soit fait deux arbres binaires sur lequel on enracine un nœud, soit est un arbre binaire vide. La récursivité est un point délicat dans l'enseignement de l'informatique[5], car son appropriation par l'apprenant demande une dose d'abstraction.

En linguistique[modifier | modifier le code]

Article détaillé : Récursivité en linguistique.

La grammaire du sanskrit de Pānini utilise déjà la récursivité au Ve siècle av. J.-C. tandis que les constructions des langues sont essentiellement récursives, par exemple, la construction des groupes nominaux : la clé de la serrure de la porte d'entrée de la maison de la rue du bout du village. Des travaux menés par le professeur Daniel Everett tendraient cependant à montrer l'absence de récursivité dans la langue Pirahã[6].

Certains auteurs ont considéré que la capacité à construire des structures récursives est propre aux systèmes de communication humaine, mais cette affirmation est aujourd'hui remise en cause par des travaux de cognition animale[7].

Un dictionnaire (dictionnaire de définition) est un exemple de récursivité : chaque mot du dictionnaire est défini par d'autres mots eux-mêmes définis par d'autres mots dans ce même dictionnaire.

Figure de Sierpiński.

Dans les arts[modifier | modifier le code]

Question book-4.svg
Cette section ne cite pas suffisamment ses sources (décembre 2017)
Pour l'améliorer, ajoutez des références vérifiables [comment faire ?] ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Dans le domaine des arts, le procédé récursif est appelé mise en abîme et c'est l'artiste Maurits Cornelis Escher qui en fait le plus grand usage ; il est connu pour ses œuvres inspirées par la récursivité. De son côté, la publicité a aussi utilisé la récursivité, rendant célèbres en France La vache qui rit et Dubonnet[3].

En biologie[modifier | modifier le code]

Question book-4.svg
Cette section ne cite pas suffisamment ses sources (décembre 2017)
Pour l'améliorer, ajoutez des références vérifiables [comment faire ?] ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

La récursivité est particulièrement présente en biologie, notamment dans les motifs de végétaux et les processus de développement. Les diatomées présentent en particulier de belles structures récursives.

En mathématiques[modifier | modifier le code]

Le triangle de Sierpiński — une récurrence de triangles formant un fractale.
Le triangle de Sierpiński — une récurrence de triangles formant une fractale.

Suite définie récursivement[modifier | modifier le code]

Article détaillé : Définition récursive d'une suite.

Fonctions récursives[modifier | modifier le code]

Articles détaillés : Algorithme récursif et Fonction récursive.

Une fonction peut être définie en matière d'elle-même. Un exemple familier est la suite de Fibonacci vue comme une fonction F : ℕ → ℕ à savoir F(n) = F(n - 1) + F(n - 2). Pour qu'une telle définition ait un sens, elle doit conduire à des valeurs immédiatement évaluables, dans le cas de la suite de Fibonacci : F(0) = 0 et F(1) = 1.

Dans les systèmes complexes[modifier | modifier le code]

Edgar Morin a très souvent utilisé le concept de récursivité et de boucle récursive, notamment dans ses ouvrages constituant la Méthode.

En neurosciences[modifier | modifier le code]

Une publicité récursive.

Récursivité, imprédicativité et auto-référence[modifier | modifier le code]

Le fait de définir un concept à partir de lui-même a été appelé par les logiciens et les mathématiciens, l'imprédicativité et cela ne doit pas être confondu avec la récursivité, bien que cela s'y apparente. On parle aussi d'auto-référence. Il existe des théories logiques imprédicatives (comme le système F dû à Jean-Yves Girard), mais elles doivent être définies avec précautions si l'on veut préserver leur cohérence, car les paradoxes ne sont pas loin. Ainsi en théorie des ensembles, le paradoxe de Russell montre qu'il ne peut pas y avoir d'ensemble constitué des ensembles qui ne se contiennent pas eux-mêmes (popularisé comme le paradoxe du barbier, en effet « si le barbier est celui qui rase ceux qui ne se rasent pas eux-mêmes, qui rase le barbier ? »). Toujours en théorie des ensembles, l'axiome de fondation proscrit les ensembles qui se contiennent eux-mêmes.

C'est pour jouer sur ces principes que des informaticiens facétieux ont défini des acronymes récursifs qui ne définissent rien puisqu'ils sont imprédicatifs et incohérents. De même, l'aphorisme suivant : « Pour comprendre le principe de récursivité, il faut d'abord comprendre le principe de récursivité », est imprédicatif et peut être considéré comme une pétition de principe.

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. « RECURSIVITÉ : Définition de RECURSIVITÉ », sur www.cnrtl.fr (consulté le 17 décembre 2017)
  2. Éditions Larousse, « Définitions : récursivité - Dictionnaire de français Larousse », sur www.larousse.fr (consulté le 22 décembre 2017)
  3. a et b Publicité Dubonnet.
  4. En algorithmique, les algorithmes récursifs sont couramment employés.
  5. (en) Matthias Hauswirth et The Education Column by Juraj Hromkovic, « If you have parents, you can learn recursion. », Bulletin of EATCS, vol. 3, no 123,‎ (lire en ligne)
  6. René Lemieux, « De la Weltanschauung du bon sauvage aux polémiques du MIT: Everett contra Chomsky », sur Laboratoire de résistance sémiotique (consulté le 5 janvier 2016).
  7. (en) A. Rey, P. Perruchet et J. Fagot, « Centre-Embedded structures are a by-product of associative learning and working memory constraints: Evidence from baboons (Papio papio) », Cognition, 123, 180-184.