Récursivité - Recursion

Une forme visuelle de récursivité connue sous le nom d' effet Droste . La femme dans cette image tient un objet qui contient une image plus petite d'elle tenant un objet identique, qui à son tour contient une image plus petite d'elle tenant un objet identique, et ainsi de suite. 1904 Boîte de cacao Droste , conçue par Jan Misset

La récursivité (adjectif : récursif ) se produit lorsqu'une chose est définie en termes d'elle-même ou de son type. La récursivité est utilisée dans une variété de disciplines allant de la linguistique à la logique . L'application la plus courante de la récursivité est en mathématiques et en informatique , où une fonction en cours de définition est appliquée dans sa propre définition. Bien que cela définisse apparemment un nombre infini d'instances (valeurs de fonction), cela est souvent fait de telle manière qu'aucune boucle infinie ou chaîne infinie de références ne peut se produire.

Définitions formelles

Ouroboros , un ancien symbole représentant un serpent ou un dragon mangeant sa propre queue.

En mathématiques et en informatique, une classe d'objets ou de méthodes présente un comportement récursif lorsqu'elle peut être définie par deux propriétés :

Un cas de base simple (ou des cas) - un scénario de fin qui n'utilise pas la récursivité pour produire une réponse
Une étape récursive — un ensemble de règles qui réduit tous les cas successifs vers le cas de base.

Par exemple, ce qui suit est une définition récursive de l' ancêtre d'une personne . L'ancêtre est soit :

Un parent ( cas de base ), ou
L'ancêtre de ses parents ( étape récursive ).

La suite de Fibonacci est un autre exemple classique de récursivité :

Fib(0) = 0

comme cas de base 1,

Fib(1) = 1

comme cas de base 2,

Pour tout entier

n > 1

,

Fib(n) = Fib(n - 1) + Fib(n - 2)

.

De nombreux axiomes mathématiques sont basés sur des règles récursives. Par exemple, la définition formelle des nombres naturels par les axiomes de Peano peut être décrite comme : « Zéro est un nombre naturel, et chaque nombre naturel a un successeur, qui est également un nombre naturel. » Par ce cas de base et cette règle récursive, on peut générer l'ensemble de tous les nombres naturels.

D'autres objets mathématiques définis de manière récursive incluent les factorielles , les fonctions (par exemple, les relations de récurrence ), les ensembles (par exemple, l' ensemble ternaire de Cantor ) et les fractales .

Il existe plusieurs définitions plus ironiques de la récursivité ; voir humour récursif .

Définition informelle

Récemment rafraîchi au levain , bouillonnant par fermentation : les appels de recette pour un pain au levain gauche au- dessus de la dernière fois a été la même recette.

La récursivité est le processus par lequel passe une procédure lorsque l'une des étapes de la procédure consiste à invoquer la procédure elle-même. Une procédure qui passe par récursivité est dite « récursive ».

Pour comprendre la récursivité, il faut reconnaître la distinction entre une procédure et le déroulement d'une procédure. Une procédure est un ensemble d'étapes basées sur un ensemble de règles, tandis que l'exécution d'une procédure implique de suivre les règles et d'effectuer les étapes.

La récursivité est liée, mais pas identique, à une référence dans la spécification d'une procédure à l'exécution d'une autre procédure.

Lorsqu'une procédure est définie comme telle, cela crée immédiatement la possibilité d'une boucle sans fin ; la récursivité ne peut être correctement utilisée dans une définition que si l'étape en question est sautée dans certains cas afin que la procédure puisse se terminer.

Mais même si elle est correctement définie, une procédure récursive n'est pas facile à exécuter pour les humains, car elle nécessite de distinguer la nouvelle de l'ancienne invocation de la procédure partiellement exécutée ; cela nécessite une certaine administration quant à l'avancement des différentes instances simultanées des procédures. Pour cette raison, les définitions récursives sont très rares dans les situations quotidiennes.

En langue

Le linguiste Noam Chomsky , parmi beaucoup d'autres, a soutenu que l'absence d'une limite supérieure sur le nombre de phrases grammaticales dans une langue, et l'absence d'une limite supérieure sur la longueur des phrases grammaticales (au-delà des contraintes pratiques telles que le temps disponible pour prononcer un ), peut être expliquée comme la conséquence de la récursivité en langage naturel.

Cela peut être compris en termes de définition récursive d'une catégorie syntaxique, telle qu'une phrase. Une phrase peut avoir une structure dans laquelle ce qui suit le verbe est une autre phrase : Dorothy pense que les sorcières sont dangereuses , dans laquelle la phrase les sorcières sont dangereuses apparaît dans la plus grande. Ainsi, une phrase peut être définie de manière récursive (très grossièrement) comme quelque chose avec une structure qui comprend un groupe nominal, un verbe et éventuellement une autre phrase. Ce n'est vraiment qu'un cas particulier de la définition mathématique de la récursivité.

Cela permet de comprendre la créativité du langage - le nombre illimité de phrases grammaticales - car il prédit immédiatement que les phrases peuvent être de longueur arbitraire : Dorothy pense que Toto soupçonne que Tin Man a dit que... . Il existe de nombreuses structures en dehors des phrases qui peuvent être définies de manière récursive, et donc de nombreuses façons dont une phrase peut intégrer des instances d'une catégorie dans une autre. Au fil des ans, les langues en général se sont révélées se prêter à ce genre d'analyse.

Récemment, cependant, l'idée généralement acceptée que la récursivité est une propriété essentielle du langage humain a été contestée par Daniel Everett sur la base de ses affirmations sur la langue Pirahã . Andrew Nevins, David Pesetsky et Cilene Rodrigues sont parmi ceux qui se sont opposés à cela. L' autoréférence littéraire peut en tout cas être considérée comme différente de la récursivité mathématique ou logique.

La récursivité joue un rôle crucial non seulement dans la syntaxe, mais aussi dans la sémantique du langage naturel . Le mot et , par exemple, peuvent être interprétés comme une fonction qui peut s'appliquer aux significations des phrases pour créer de nouvelles phrases, et de même pour les significations des phrases nominales, les significations des phrases verbales et autres. Il peut également s'appliquer aux verbes intransitifs, aux verbes transitifs ou aux verbes ditransitifs. Afin de lui fournir une dénotation unique qui soit suffisamment flexible et qui soit généralement définie de manière à pouvoir prendre n'importe lequel de ces différents types de significations comme arguments. Cela peut être fait en le définissant pour un cas simple dans lequel il combine des phrases, puis en définissant les autres cas de manière récursive en termes de simple.

Une grammaire récursive est une grammaire formelle qui contient des règles de production récursives .

Humour récursif

Une page Wikipédia récursive

La récursivité est parfois utilisée avec humour dans les manuels d'informatique, de programmation, de philosophie ou de mathématiques, généralement en donnant une définition circulaire ou une autoréférence , dans laquelle l'étape récursive putative ne se rapproche pas d'un cas de base, mais conduit plutôt à une régression infinie . Il n'est pas rare que de tels livres incluent une entrée de blague dans leur glossaire du type :

Récursivité, voir Récursivité .

Une variation se trouve à la page 269 dans l' index de certaines éditions du livre de Brian Kernighan et Dennis Ritchie , The C Programming Language ; l'entrée d'index se référence récursivement à elle-même ("récursion 86, 139, 141, 182, 202, 269"). Les premières versions de cette blague peuvent être trouvées dans Let's talk Lisp de Laurent Siklóssy (publié par Prentice Hall PTR le 1er décembre 1975, avec une date de copyright de 1976) et dans Software Tools de Kernighan et Plauger (publié par Addison-Wesley Professional le 11 janvier 1976). La blague apparaît également dans L'environnement de programmation UNIX de Kernighan et Pike. Il n'apparaissait pas dans la première édition de The C Programming Language . La blague fait partie du folklore de la programmation fonctionnelle et était déjà répandue dans la communauté de la programmation fonctionnelle avant la publication des livres susmentionnés.

Une autre blague est que "Pour comprendre la récursivité, vous devez comprendre la récursivité." Dans la version anglaise du moteur de recherche Web Google, lorsqu'une recherche de « recursion » est effectuée, le site propose « Vouliez-vous dire : récursivité ». Une autre forme est la suivante, d' Andrew Plotkin : "Si vous savez déjà ce qu'est la récursivité, souvenez-vous simplement de la réponse. Sinon, trouvez quelqu'un qui se tient plus près de Douglas Hofstadter que vous, puis demandez-lui ce qu'est la récursivité."

Les acronymes récursifs sont d'autres exemples d'humour récursif. PHP , par exemple, signifie "PHP Hypertext Preprocessor", WINE signifie "WINE Is Not an Emulator", GNU signifie "GNU's not Unix", et SPARQL désigne le "SPARQL Protocol and RDF Query Language".

En mathématiques

Le triangle de Sierpinski - une récursion confinée de triangles qui forment une fractale

Ensembles définis de manière récursive

Exemple : les nombres naturels

L'exemple canonique d'un ensemble défini récursivement est donné par les nombres naturels :

0 est dans

\mathbb {N}

si n est dans , alors n + 1 est dans

\mathbb {N}

\mathbb {N}

L'ensemble des nombres naturels est le plus petit ensemble satisfaisant les deux propriétés précédentes.

En logique mathématique, les axiomes de Peano (ou postulats de Peano ou axiomes de Dedekind-Peano), sont des axiomes pour les nombres naturels présentés au XIXe siècle par le mathématicien allemand Richard Dedekind et par le mathématicien italien Giuseppe Peano . Les axiomes de Peano définissent les nombres naturels se référant à une fonction successeur récursive et l'addition et la multiplication en tant que fonctions récursives.

Exemple : procédure de preuve

Un autre exemple intéressant est l'ensemble de toutes les propositions "prouvables" dans un système axiomatique qui sont définies en termes d'une procédure de preuve qui est définie inductivement (ou récursivement) comme suit :

Si une proposition est un axiome, c'est une proposition prouvable.
Si une proposition peut être dérivée de vraies propositions accessibles au moyen de règles d'inférence, c'est une proposition prouvable.
L'ensemble des propositions prouvables est le plus petit ensemble de propositions satisfaisant à ces conditions.

Règles de subdivision finie

Les règles de subdivision finie sont une forme géométrique de récursivité, qui peut être utilisée pour créer des images de type fractal. Une règle de subdivision commence par une collection de polygones étiquetés par un nombre fini d'étiquettes, puis chaque polygone est subdivisé en polygones étiquetés plus petits d'une manière qui ne dépend que des étiquettes du polygone d'origine. Ce processus peut être itéré. La technique standard des « tiers moyens » pour créer l' ensemble de Cantor est une règle de subdivision, tout comme la subdivision barycentrique .

Récursivité fonctionnelle

Une fonction peut être définie de manière récursive en termes d'elle-même. Un exemple familier est la suite de nombres de Fibonacci : F ( n ) = F ( n − 1) + F ( n − 2). Pour qu'une telle définition soit utile, elle doit être réductible à des valeurs définies de manière non récursive : dans ce cas F (0) = 0 et F (1) = 1.

Une fonction récursive célèbre est la fonction d'Ackermann , qui, contrairement à la suite de Fibonacci, ne peut être exprimée sans récursivité.

Preuves impliquant des définitions récursives

L'application de la technique standard de preuve par cas à des ensembles ou des fonctions définis de manière récursive, comme dans les sections précédentes, donne une induction structurelle - une puissante généralisation de l'induction mathématique largement utilisée pour dériver des preuves en logique mathématique et en informatique.

Optimisation récursive

La programmation dynamique est une approche de l' optimisation qui reformule un problème d'optimisation à plusieurs périodes ou à plusieurs étapes sous forme récursive. Le résultat clé de la programmation dynamique est l' équation de Bellman , qui écrit la valeur du problème d'optimisation à un moment antérieur (ou à une étape antérieure) en fonction de sa valeur à un moment ultérieur (ou à une étape ultérieure).

Le théorème de récursivité

En théorie des ensembles , il s'agit d'un théorème garantissant l'existence de fonctions définies récursivement. Étant donné un ensemble $X$ , un élément $a$ de $X$ et une fonction $f : X \to X$ , le théorème énonce qu'il existe une fonction unique (où désigne l'ensemble des nombres naturels incluant zéro) telle que $F:\mathbb {N} \to X$ $\mathbb {N}$

{\style d'affichage F(0)=a}

{\style d'affichage F(n+1)=f(F(n))}

pour tout entier naturel $n$ .

Preuve d'unicité

Prenons deux fonctions et telles que : $F:\mathbb {N} \to X$ $G:\mathbb {N} \to X$

{\style d'affichage F(0)=a}

{\style d'affichage G(0)=a}

{\style d'affichage F(n+1)=f(F(n))}

{\style d'affichage G(n+1)=f(G(n))}

où $a$ est un élément de $X$ .

Il peut être prouvé par induction mathématique que $F (n) = G (n)$ pour tous les nombres naturels $n$ :

Cas de base :

F (0) = a = G (0)

donc l'égalité est vraie pour

n = 0

.

Étape inductive : Supposons

F (k) = G (k)

pour certains . Alors

F

(

k

+ 1) =

f

(

F

(

k

)) =

f

(

G

(

k

)) =

G

(

k

+ 1)

.

k\in \mathbb {N}

Donc

F (k) = G (k)

implique

F (k + 1) = G (k + 1)

.

Par récurrence, $F (n) = G (n)$ pour tout . $n\in \mathbb {N}$

En informatique

Une méthode courante de simplification consiste à diviser un problème en sous-problèmes du même type. En tant que technique de programmation informatique , cela s'appelle diviser pour régner et est la clé de la conception de nombreux algorithmes importants. Diviser pour mieux régner sert d'approche descendante à la résolution de problèmes, où les problèmes sont résolus en résolvant des instances de plus en plus petites. Une approche contraire est la programmation dynamique . Cette approche sert d'approche ascendante, où les problèmes sont résolus en résolvant des instances de plus en plus grandes, jusqu'à ce que la taille souhaitée soit atteinte.

Un exemple classique de récursivité est la définition de la fonction factorielle , donnée ici en code C :

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

La fonction s'appelle récursivement sur une version plus petite de l'entrée (n - 1)et multiplie le résultat de l'appel récursif par n, jusqu'à atteindre le cas de base , de manière analogue à la définition mathématique de factoriel.

La récursivité dans la programmation informatique est illustrée lorsqu'une fonction est définie en termes de versions plus simples et souvent plus petites d'elle-même. La solution au problème est ensuite conçue en combinant les solutions obtenues à partir des versions les plus simples du problème. Un exemple d'application de la récursivité est dans les analyseurs syntaxiques pour les langages de programmation. Le grand avantage de la récursivité est qu'un ensemble infini de phrases, de conceptions ou d'autres données possibles peut être défini, analysé ou produit par un programme informatique fini.

Les relations de récurrence sont des équations qui définissent une ou plusieurs séquences de manière récursive. Certains types spécifiques de relation de récurrence peuvent être "résolus" pour obtenir une définition non récursive (par exemple, une expression de forme fermée ).

L'utilisation de la récursivité dans un algorithme présente à la fois des avantages et des inconvénients. Le principal avantage est généralement la simplicité des instructions. Le principal inconvénient est que l'utilisation de la mémoire des algorithmes récursifs peut augmenter très rapidement, ce qui les rend peu pratiques pour les instances plus importantes.

En biologie

Des formes qui semblent avoir été créées par des processus récursifs apparaissent parfois chez les plantes et les animaux, comme dans les structures ramifiées dans lesquelles une grande partie se ramifie en deux ou plusieurs parties plus petites similaires. Le brocoli romanesco en est un exemple .

Dans l'art

Poupées récursives : l'ensemble original de poupées Matriochka par Zvyozdochkin et Malyutin , 1892

Face avant de Giotto de Stefaneschi Triptych , 1320, contient de manière récursive une image de lui - même (tenue en place par la figure agenouillée dans le panneau central).

La poupée russe ou poupée matriochka est un exemple artistique physique du concept récursif.

La récursion est utilisée dans les peintures depuis le Triptyque Stefaneschi de Giotto , réalisé en 1320. Son panneau central contient la figure agenouillée du Cardinal Stefaneschi, tenant le triptyque lui-même comme une offrande.

La Print Gallery de MC Escher (1956) est une estampe qui représente une ville déformée contenant une galerie qui contient récursivement l'image, et donc à l' infini .

Voir également

Les références

Bibliographie

Dijkstra, Edsger W. (1960). "Programmation récursive". Numerische Mathematik . 2 (1) : 312-318. doi : 10.1007/BF01386232 . S2CID 127891023 .
Johnsonbaugh, Richard (2004). Mathématiques discrètes . Prentice Hall. ISBN 978-0-13-117686-7.
Hofstadter, Douglas (1999). Gödel, Escher, Bach : une éternelle tresse dorée . Livres de base. ISBN 978-0-465-02656-2.
Shoenfield, Joseph R. (2000). Théorie de la récursion . AK Peters Ltd. ISBN 978-1-56881-149-9.
Causey, Robert L. (2001). Logique, ensembles et récursivité . Jones & Bartlett. ISBN 978-0-7637-1695-0.
Cori, René ; Lascar, Daniel ; Pelletier, Donald H. (2001). Théorie de la récursion, Théorèmes de Gödel, Théorie des ensembles, Théorie des modèles . Presses de l'Université d'Oxford. ISBN 978-0-19-850050-6.
Barwise, Jon ; Mousse, Lawrence S. (1996). Cercles vicieux . Centre universitaire de Stanford pour l'étude de la langue et de l'information. ISBN 978-0-19-850050-6. - propose un traitement de corecursion .
Rosen, Kenneth H. (2002). Mathématiques discrètes et ses applications . Collège McGraw-Hill. ISBN 978-0-07-293033-7.
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L.; Stein, Clifford (2001). Introduction aux algorithmes . Mit Pr. ISBN 978-0-262-03293-3.
Kernighan, B.; Ritchie, D. (1988). La programmation en langage C . Prentice Hall. ISBN 978-0-13-110362-7.
Stokey, Nancy ; Robert Lucas ; Edward Prescott (1989). Méthodes récursives en dynamique économique . Presses de l'Université Harvard. ISBN 978-0-674-75096-8.
Hungerford (1980). Algèbre . Springer. ISBN 978-0-387-90518-1., premier chapitre sur la théorie des ensembles.

Languages

In other projects