La récursivité partout

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

• le cours d'Olivier Lécluse
• le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
• le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
• la ressource Eduscol sur la récursivité
• le cour e-nsi sur la récursivité
• le cours de mon collègue Pierre Duclosson

🔖 Synthèse de ce qu'il faut retenir pour le bac

Objet récursif

Point de cours 2

Lorsque la définition d'un objet fait appel à l'objet lui même, on parle de définition récursive.

Exemple 2

On trouve beaucoup de définitions récursives en informatique :

• pour définir une structure de données récursive :
  • un arbre binaire est soit vide, soit un noeud qui a pour fils deux arbres binaires
  • une liste est soit vide, soit un couple constitué d'une valeur et d'une référence vers une liste
• dans des acronymes, pratique héritée des communautés de hackers des campus des années 1970 :
  • le sigle du projet de système d'exploitation libre GNU est un acronyme négatif : GNU'S NOT UNIX
  • le sigle du langage de serveur Web PHP: Hypertext Preprocessor contient sa définition : PHP: Hypertext Preprocessor

Récursivité en géométrie et dans l'art

Exemple 3 : figures fractales

Une figure fractale présente une structure similaire à toutes les échelles.

On peut en donner une définition récursive : un élément d'une figure fractale est une figure fractale.

Le terme fractale, qui vient du latin fractus (cassé), est apparu pour la première fois en 1975, dans le livre Les objets fractals : forme, objet et dimension, de Benoît Mandelbrot, ancien élève du lycée du Parc.

Les premières courbes fractales sont apparues au début du XX siècle avec par exemple la courbe de Von Koch.

On peut la créer à partir d'un segment de droite, en modifiant récursivement chaque segment de droite (cas de base) de la façon suivante (réduction) :

• Étape 1 : On divise le segment de droite en trois segments de longueurs égales.

• Étape 2 : On construit un triangle équilatéral ayant pour base le segment médian de la première étape.

• Étape 3 : On supprime le segment médian qui était la base du triangle de la deuxième étape.

Source : article de Wikipedia.

Une structure fractale étant infinie, on ne peut représenter qu'une courbe approchée d'une courbe fractale par itérations successives.

En pratique, il est plus simple de procéder récursivement à partir de la dernière itération pour construire la courbe approchée par réductions successives jusqu'au cas de base.

On peut mettre en évidence le cas de base et la réduction pour la courbe de Koch à partir des trois premières itérations.

Cas de base: itération 1

Itération 2

Itération 3 avec réduction

Flocon de Von Koch

Exemple 4

Les figures récursives qui se contiennent elles-mêmes sont fréquentes dans la publicité ou chez certains artistes comme M.C. Escher qui s'est intéressé à la représentation de l'infini.

Publicité de la Vache Qui Rit

Source : Création de l'artiste visuel Polonais Feliks Tomasz Konczakowski

Tableau de M.C. Escher

Dans une galerie d'art, un jeune homme regarde une estampe. En fait le jeune homme est dans le tableau qu'il est en train de regarder. C'est une mise en abyme.

Récursivité dans le langage et la littérature

Exemple 5

Citons l'article de Wikipédia sur la récursivité :

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

En littérature, la récursivité peut s'exprimer à travers le procédé de mise en abyme où une oeuvre est représentée dans une oeuvre similaire. Par exemple dans son roman Les Faux Monnayeurs, André Gide introduit un personnage en train d'écrire un roman intitulé Les Faux Monnayeurs.

Ce procédé se retrouve également au cinéma (Last Action Hero) ou au théâtre (L'illusion comique).