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 de la démarche. Ainsi, les cas suivants constituent des cas concrets de récursivité :

  • 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[1]
  • Définir un concept en invoquant le même concept
  • Écrire un algorithme qui s'invoque lui-même[2].

Récursivité en informatique et en logique[modifier | modifier le code]

En informatique et en logique, une fonction ou plus généralement un algorithme qui contient un appel à elle-même est dite récursive. Deux fonctions peuvent s'appeler l'une l'autre, on parle alors de récursivité croisée.

Récursivité 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.

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

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

Récursivité dans les arts[modifier | modifier le code]

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

Récursivité en biologie[modifier | modifier le code]

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.

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 :

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

  1. a et b Publicité Dubonnet
  2. En algorithmique, les algorithmes récursifs sont couramment employés.
  3. Rey, A., Perruchet, P. & Fagot, J. (2011). Centre-Embedded structures are a by-product of associative learning and working memory constraints: Evidence from baboons (Papio papio). Cognition, 123, 180-184.