Récursivité

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 des images similaires, de définir un concept en invoquant le même concept[1].

L'algorithme récursif constitue un exemple typique des processus récursifs.

Sommaire

Récursivité en informatique et en logique

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

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.

Figure de Sierpinski

Récursivité dans les arts

Dans le domaine des arts, le procédé récursif est appelé Mise en abyme 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[2].

Récursivité en biologie

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

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 est imprédicatif, l'aphorisme suivant: "Pour comprendre le principe de récursivité, il faut d'abord comprendre le principe de récursivité", on dirait plutôt que c'est une pétition de principe.

Voir aussi

Sur les autres projets Wikimedia :

Références


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Recursivite — Récursivité La récursivité est une démarche qui consiste à faire référence à ce qui fait 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… …   Wikipédia en Français

  • RÉCURSIVITÉ — Les (semi ) fonctions récursives ont été introduites pour donner un équivalent mathématique à la notion métamathématique intuitive de (semi ) fonction effectivement ou mécaniquement calculable (cf. LOGIQUE MATHÉMATIQUE, chap. 4). Par souci de… …   Encyclopédie Universelle

  • récursivité — ● n. f. ►ALGO Voir récursivité. (© Jargon File 3.0.0). * Le fait pour un programme ou une procédure de s appeler au moins une fois lui même. Le principe de la récursivité est essentiel en programmation, il permet de résoudre de façon élégante la… …   Dictionnaire d'informatique francophone

  • RÉCURSIVITÉ (linguistique) — RÉCURSIVITÉ, linguistique Est dit récursif, dans la linguistique générative, tout élément qui présente la propriété de se reproduire dans l’algorithme d’une structure de phrase à la fois comme constituant et comme constitué, c’est à dire à droite …   Encyclopédie Universelle

  • 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… …   Wikipédia en Français

  • Récursivité (linguistique) — En linguistique, la récursivité est une propriété d une règle de construction syntaxique pouvant se répéter un nombre indéfini de fois à partir du résultat qu elle produit. En morphologie et en lexicologie, elle s observe dans la formation même… …   Wikipédia en Français

  • Récursivité gauche — La récursivité gauche est un type de récursivité. Une grammaire formelle est dite récursive gauche si elle s’écrit sous la forme suivante :       E → E v     tel que v ne commence pas par E. Sommaire 1 Pourquoi… …   Wikipédia en Français

  • Récursivité croisée — Récursion mutuelle La récursion mutuelle est une récursion où deux (ou plus) fonctions mathématiques ou programmatiques sont définies l une en termes de l autre. Par exemple, deux fonctions A(x) and B(x) définies comme suit : La récursion… …   Wikipédia en Français

  • Factorisation par récursivité activée par réseau — Factoring via Network Enabled Recursion (FAFNER) (Factorisation par récursivité activée par réseau) était un projet datant de 1995 pour essayer de résoudre le problème de factorisation de RSA 130. C était un effort de criblage par Internet à… …   Wikipédia en Français

  • Droste — Récursivité La récursivité est une démarche qui consiste à faire référence à ce qui fait 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… …   Wikipédia en Français

Share the article and excerpts

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