Voir la source de Récursivité

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 une démarche dont la description mène à la répétition d'une même règle{{sfn|cnrtl|texte=CNRTL: RECURSIVITÉ}}{{,}}{{sfn|Larousse|texte=Larousse: récursivité}}. 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 ;
* définir un concept en invoquant ce même concept ;
* écrire un [[algorithme]] qui s'invoque lui-même<ref group=note>En algorithmique, les [[algorithme récursif|algorithmes récursifs]] sont couramment employés.</ref> ;
* définir une structure à partir de l'une au moins de ses sous-structures ;
* faire pointer un article de Wikipédia vers lui-même ou vers un article qui, par une succession de pointeurs, pointe vers l'article dont on est parti ; ainsi dans l'article que vous lisez, l'expression « pétition de principe » pointe vers un article qui pointe vers le présent article<ref group=note>Notons que le système de wiki détecte les liens hypertextes qui pointent sur la page les mentionnant et les supprime afin d'éviter des problèmes de boucle aux robots parcourant les pages.</ref>.

== En informatique ==
{{Article détaillé|Algorithme récursif|Fonction récursive}}
[[Fichier:Binary tree.svg|vignette|Un arbre binaire est une structure de données récursive. L’arbre représenté, contenant les neuf éléments {2, 7, 2, 6, 5, 11, 5, 9, 4}, est constitué d’un {{nobr|nœud 2}} portant à gauche un arbre à cinq éléments {7, 2, 6, 5, 11} et à droite un arbre à trois élements {5, 9, 4}. Ce dernier est constitué d’un {{nobr|nœud 5}} portant à gauche un arbre vide, et à droite un arbre à deux éléments {9, 4}. Ce dernier est constitué d’un {{nobr|nœud 9}} portant à gauche un arbre à un élément {4}, et à droite un arbre vide. L’arbre à un élément {4} est constitué d’un {{nobr|nœud 4}} portant deux arbres vides.]]
En [[informatique]], la définition de certaines [[Structure de données|structures de données]], comme les [[liste (informatique)|listes]] ou les [[arbre (informatique)|arbres]], est récursive : elle mentionne le type de données en train d’être défini. Par exemple (voir la figure) un [[arbre binaire]] est soit vide, soit un nœud portant deux [[sous-arbre|arbres binaires plus petits]].

Par ailleurs, une [[fonction (informatique)|fonction]] ou plus généralement un [[algorithme]] peut contenir un ou des appels à lui-même, auquel cas il est dit [[Algorithme récursif|récursif]]. Ce procédé est en particulier employé pour traiter les structures de données récursives, ainsi que pour réaliser le paradigme algorithmique « [[Diviser pour régner (informatique)|diviser pour régner]] ».

Deux [[Type (informatique)|types de données]] peuvent, dans leur définition respective, se mentionner l'un l'autre ; de même, deux algorithmes peuvent s'appeler l'un l'autre. On parle alors de [[récursivité croisée]], ou mutuelle.

Comme l’usage de [[structure de contrôle#Boucles|boucles]], la récursivité permet d’effectuer un nombre d’opérations non connu à l’avance car déterminé par les entrées du programme ; ces deux procédés permettent aussi d’écrire des programmes qui ne se [[terminaison d'un algorithme|terminent]] pas. 

La récursivité est un point délicat dans l'enseignement de l'informatique{{sfn|Hauswirth|Hromkovič|2017}}, car son appropriation par l'apprenant demande une dose d'abstraction.

== En linguistique ==
{{article détaillé|Récursivité (linguistique){{!}}Récursivité en linguistique}}
[[Noam Chomsky]], linguiste américain renommé, parmi d'autres, affirme que le manque d'une limite supérieure en ce qui concerne le nombre de phrases grammaticales ainsi que leur longueur (en restant dans le domaine de ce qui est pratique) est le résultat de la récursivité du langage naturel{{sfn|Pinker|2008}}{{,}}{{sfn|Pinker|Jackendoff|2005}}.

Cela se comprend à l'aide d'une définition récursive d'une catégorie syntaxique, comme une phrase. Une phrase peut posséder une structure dans laquelle une phrase enchâssée se trouve après le verbe : ''Dorothée pense que les sorcières sont dangereuses'', dans laquelle la phrase ''les sorcières sont dangereuses'' se trouve dans une phrase déjà présente. Donc, une phrase peut être définie récursivement (à peu près) comme quelque chose qui possède une structure qui inclut une phrase nominale, un verbe et une autre phrase (optionnelle). C'est vraiment un cas spécial dans lequel la définition mathématique de la récursivité se manifeste.

La récursivité joue un rôle important non seulement en syntaxe, mais aussi dans la [[Sémantique|sémantique du langage naturel]]. Le mot ''et'', par exemple, peut être considéré comme une fonction qui peut s'appliquer aux sens des phrases pour créer de nouvelles phrases. Cela s'effectue également en ce qui concerne les sens des phrases nominales, verbales, parmi d'autres formes phrasales. C'est aussi le cas pour les verbes transitifs, intransitifs ou même ditransitifs. Afin de lui fournir une seule dénotation suffisamment flexible, ''et'' se définit tout simplement comme ayant la possibilité de représenter des arguments à travers n'importe quelles formes significatives. Cela peut s'effectuer en définissant ''et'' pour un cas simple dans lequel on combine des phrases, puis définir les autres cas récursivement en termes du cas simple{{sfn|Portner|Partee|2002}}.

La grammaire du [[sanskrit]] de [[Pānini]] utilise déjà la récursivité au {{Ve siècle av. J.-C.}} 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ã (langue)|Pirahã]]{{sfn|Lemieux|2013}}.

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{{sfn|Rey|Perruchet|Fagot|2012}}.

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.

[[Fichier:Sierpinski square.png|thumb|upright=0.5|Figure de [[Wacław Sierpiński|Sierpiński]].]]

== Dans les arts ==
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<!-- Source requise --> ; il est connu pour ses œuvres inspirées par la récursivité<ref>{{article | titre=La mise en abyme dans les arts | périodique=[[École polytechnique fédérale de Lausanne]] (Énoncé théorique de master) | date=janvier 2015 | passage=27-28 | prénom1=Odile | nom1=Allimann| prénom2=Émilie | nom2=Revaz | lire en ligne=https://infoscience.epfl.ch/record/215629/files/2015_005_allimann_revaz_enonce_La_mise_en_abyme_dans_les_arts.pdf | consulté le=8 décembre 2022 | format=pdf}}.</ref>. De son côté, la publicité a aussi utilisé la récursivité, rendant célèbres en France [[La vache qui rit]] et [[Dubonnet]]<ref>{{article | titre=L’effet Vache-qui-rit ou les phrases emboîtées | périodique=[[Sciences et Avenir]] | date=juillet-août 2020 | lire en ligne=https://www.sciencesetavenir.fr/fondamental/mathematiques/l-effet-vache-qui-rit-ou-les-phrases-emboitees_145886 | consulté le=8 décembre 2022}}.</ref>{{,}}<ref>{{article | titre=La Mise en abyme imagée | périodique=Textimage | numéro=4 | date=hiver 2012 | passage=5 | prénom=J.-M. | nom=Limoges | lire en ligne=https://www.revue-textimage.com/06_image_recit/limoges.pdf | consulté le=8 décembre 2022 | format=pdf}}.</ref>.

== En biologie ==
{{Section à sourcer|date=décembre 2017}}
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ée]]s présentent en particulier de belles structures récursives.<gallery>
Fichier:Sunflower with a bee.jpg|Une fleur de tournesol.
Fichier:Diatom 1.png|Une diatomée centrale.
Fichier:NautilusCutawayLogarithmicSpiral.jpg|Coupe sagittale d'une coquille de [[Nautilus (mollusque)|nautile]].
</gallery>

== En mathématiques ==
[[Fichier:Sierpinski_triangle.svg|alt=Le triangle de Sierpiński — une récurrence de triangles formant un fractale.|vignette|250x250px|Le [[triangle de Sierpiński]] — une récurrence de triangles formant une [[fractale]].]]

=== Suite définie récursivement ===
{{Article détaillé|Définition par récurrence#Définition par récurrence sur la suite des valeurs{{!}}Définition récursive d'une suite}}

=== Fonctions récursives ===
{{article détaillé |Algorithme récursif|Fonction récursive}}
Une [[Fonction (mathématiques)|fonction]] peut être définie en fonction d'elle-même. Un exemple familier est la [[suite de Fibonacci]] vue comme une fonction <math>F: \N \to \N</math>, à savoir <math>F(n) = F(n - 1) + F(n - 2)</math>. 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 on pose <math>F(0) = 0</math> et <math>F(1) = 1</math>.

=== Un exemple : le flocon de Koch ===
Le [[flocon de Koch]] est une figure fractale utilisant un [[Système de fonctions itérées|procédé simple de récursivité]].
[[Fichier:Koch anime.gif|vignette|Le flocon de Koch - une récurrence de triangles formant une fractale.]]
À l'étape initiale, on a un triangle équilatéral. L'étape suivante consiste à construire trois triangles équilatéraux en prenant pour base le tiers central de chacun des côtés du triangle initial. En répétant ce procédé d'abord pour les trois nouveaux triangles, puis autant de fois qu'on le veut, on obtient le flocon de Koch.

== Récursivité, imprédicativité et auto-référence ==
[[Fichier:Droste.jpg|thumb|upright=0.5|Une publicité récursive.]]
Définir un concept à partir de lui-même a été appelé par les logiciens et les mathématiciens ''[[imprédicativité]]'', notion qui ne doit pas être confondue avec celle de ''récursivité'' bien qu'elle lui soit apparentée. 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écaution 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 [[acronymie récursive|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é »{{Référence nécessaire|date=29 décembre 2018}}, est imprédicatif et peut être considéré comme une [[pétition de principe]].

== En systémique, neurosciences et systèmes complexes, cognition ==
[[Edgar Morin#La pensée qui relie|Edgar Morin]] a très souvent utilisé le concept de récursivité, qu'il appelle ''boucle récursive'', notamment dans ses ouvrages constituant ''[[Edgar Morin#La Méthode|la Méthode]]''.
La boucle récursive est à causalité circulaire : la conséquence agit sur la cause de l'effet. La plasticité cérébrale, composée de la [[plasticité neuronale]] et de la  [[plasticité synaptique]], est un exemple de boucle récursive. Par exemple : le cerveau a la capacité de piloter l'enchaînement des différents muscles de commande lors du premier apprentissage d'un mouvement complexe (swing du golf). La répétition du geste modifie les réseaux neuronaux et synaptiques qui deviennent ainsi aptes à de nouvelles capacités : l'apprentissage des gestes pour les effets donnés à la balle.

{{Citation|'''Le principe de récursion''' organisationnelle va au-delà du principe de la rétroaction ({{Langue|en|feed-back}}); il dépasse la notion de régulation pour celle d'autoproduction et [[auto-organisation]]. C'est une boucle génératrice dans laquelle les produits et les effets sont eux-mêmes producteurs et causateurs de ce qui les produit. [&hellip;] Les individus humains produisent la société dans et par leurs interactions, mais la société, en tant que tout [[Émergence|émergeant]], produit l'humanité de ces individus en leur apportant le langage et la culture}}{{sfn|Morin|Le Moigne|1999}}.

Dans le {{6e}} opus de ''La Méthode'', Edgar Morin propose la récursion éthique.

{{Citation|L'auto-examen, l'autocritique et la gymnastique psychique coïncident en la pratique récursive qui consiste à évaluer nos évaluations, juger nos jugements, critiquer nos critiques. [&hellip;]

La récursion éthique met également en boucle compréhension/explication (c'est-à-dire examen objectif/subjectif) : toute explication doit être complétée par la compréhension, toute compréhension doit être complétée par l'explication.

La récursion éthique, enfin, nous renforce immunologiquement contre notre tendance à culpabiliser autrui, devenant bouc émissaire de nos fautes}}{{sfn|Morin|2004}}.

== Notes et références ==
=== Notes ===
{{Traduction/Référence|lang1=en|art1=Recursion|id1=743138450|type=note}}
{{Notes}}

=== Références ===
{{Références}}

== Annexes ==
{{Autres projets|wiktionary=récursivité|wiktionary2=récursion|wiktionary3=récurrence}}

=== Bibliographie ===
* {{Ouvrage |prénom1=Edgar|nom1=Morin |titre=La méthode |sous-titre=L'éthique |tome=6 |éditeur=[[Éditions du Seuil|Seuil]] |année=2004 |pages totales=285 |passage=120-121 |isbn=978-2-7578-0183-3 |libellé=Morin 2004}} ;
* {{Ouvrage |prénom1=Edgar|nom1=Morin |prénom2=Jean-Louis|nom2=Le Moigne |titre=L'intelligence de la complexité |lieu=Paris |éditeur=[[Éditions L'Harmattan|L'Harmattan]] |année=1999 |pages totales=332 |passage=255 |isbn=978-2-7384-8085-9 |lire en ligne=https://books.google.com/books?id=KDFU7u-Dw1QC&printsec=frontcover|libellé=Morin et Le Moigne 1999}}, reprise avec de legères modifications de {{harvsp|Morin|1995}} ;
* {{Article |prénom1=Edgar|nom1=Morin |titre=Vers un nouveau paradigme |périodique=Sciences humaines |numéro=47 |date=février 1995 |pages=20-23 |passage=22-23 |libellé=Morin 1995}} ;
* {{Article|langue=en|prénom1=Matthias|nom1=Hauswirth|nom2=Hromkovič|prénom2=Juraj|lien auteur2= Juraj Hromkovič|titre= The Education Column|sous-titre=If you have parents, you can learn recursion|périodique=Bulletin of EATCS|volume=3|numéro=123|date=2017-10-12|lire en ligne=http://bulletin.eatcs.org/index.php/article/view/516|consulté le=2017-12-17|libellé=Hauswirth et Hromkovič 2017}} ; <!-- lien mort ; janvier 2025 -->
* {{Ouvrage|nom1=Pinker|prénom1=Steven|langue=en|titre=The language instinct|sous-titre=the new science of language and the mind|éditeur=Penguin|année=2008|pages totales=494|isbn=978-0-14-103765-3|isbn2=0-14-103765-2|oclc=277159505|lire en ligne=http://worldcat.org/oclc/277159505|consulté le=2020-04-06|libellé=Pinker 2008}} ;
* {{Article |langue=en |prénom1=Steven |nom1=Pinker |prénom2=Ray |nom2=Jackendoff |titre=The faculty of language|sous-titre=what's special about it? |périodique=Cognition |volume=95 |numéro=2 |date=2005-03 |doi=10.1016/j.cognition.2004.08.004 |lire en ligne=https://linkinghub.elsevier.com/retrieve/pii/S0010027704001763 |consulté le=2020-04-06 |pages=201-236|libellé=Pinker et Jackendoff 2005}} ;
* {{Ouvrage |langue=en |prénom1=Paul |nom1=Portner |prénom2=Barbara H. |nom2=Partee |titre=Formal Semantics |éditeur= |collection=The Essential Readings |date=2002-01-01 |isbn=978-0-631-21541-7 |doi=10.1002/9780470758335 |lire en ligne=http://dx.doi.org/10.1002/9780470758335 |consulté le=2020-04-06|libellé=Portner et Partee 2002}} ;
* {{Lien web|langue = fr-FR|prénom1=René|nom1=Lemieux|titre = De la {{Langue|de|Weltanschauung}} du bon sauvage aux polémiques du MIT|sous-titre=Everett contra Chomsky|url = http://resistancesemiotique.org/de-la-weltanschauung-des-piraha-aux-polemiques-du-mit-everett-contra-chomsky/|site = Laboratoire de résistance sémiotique|année=2013|mois=12|jour=11|consulté le = 5 janvier 2016|libellé=Lemieux 2013}} ;
* {{article|langue=en|prénom1=Arnaud|nom1=Rey|prénom2=Pierre|nom2=Perruchet|prénom3=Joël|nom3=Fagot|titre=Centre-embedded structures are a by-product of associative learning and working memory constraints|sous-titre=evidence from baboons (Papio Papio)|périodique=Cognition|pmid=22225966|DOI=10.1016/J.COGNITION.2011.12.005|numéro =1|volume=123|pages=180-184|année=2012|mois=04|libellé=Rey, Perruchet et Fagot 2012}}.

=== Liens externes ===
* {{Dictionnaires}}
* {{Autorité}}
* {{Lien web|langue=fr|titre=RECURSIVITÉ|sous-titre=Définition de RECURSIVITÉ|url=http://www.cnrtl.fr/definition/recursivit%C3%A9|site=www.cnrtl.fr|consulté le=2017-12-17|libellé=CNRTL: RECURSIVITÉ|id=cnrtl|éditeur=[[Centre national de ressources textuelles et lexicales]]}} ;
* {{Lien web|langue=fr|titre=Définitions|sous-titre=récursivité|éditeur=[[éditions Larousse]]|périodique=Dictionnaire de français Larousse|url=http://www.larousse.fr/dictionnaires/francais/r%C3%A9cursivit%C3%A9/67271|site=www.larousse.fr|consulté le=2017-12-22|libellé=Larousse: récursivité|id=Larousse}}.

=== Articles connexes ===
{{colonnes|nombre=2|1=
* [[Acronymie récursive]]
* [[Algorithme récursif]]
* [[Art algorithmique]]
* [[Autonymie]]
* [[Autopoïèse]]
* [[Calculabilité]]
* [[Causalité (physique)|Causalité]]
* {{lien | langue=en| fr = Corécursion| trad= Corecursion}}
* [[Définition par récurrence]]
* [[Dixième problème de Hilbert]]
* [[Fractale]]
* [[Fonction récursive]]
* [[Fonction d'Ackermann]]
* [[Fonction de Sudan]]
* [[Fonction récursive primitive]]
* [[Mise en abyme]]
* [[Pétition de principe]]
* [[Récursion terminale]]
* [[Récursion mutuelle]]
* [[Suite récurrente]]
* [[Tapis de Sierpiński]]
}}
{{Portail|Mathématiques|Logique|Informatique}}

[[Catégorie:Méthode algorithmique]]
[[Catégorie:Autoréférence]]
[[Catégorie:Structure de contrôle]]