Aller au contenu

Présentation de la récursivité

I. Dans la nature⚓︎

Remarquons qu'un chou romanesco est constitué d'un ensemble de « florettes » pyramidales disposées en couronnes spiralées. Sa forme géométrique (dite fractale) est très particulière et décorative.

Romanesco

Crédits : Ivar Leidus - CC BY-SA 4.0 - via Wikimedia Commons

II. Le principe⚓︎

Bien lire et comprendre la bande dessinée suivante, dessinée par Gilles LASSUS :

BD Gilles Lassus

III. La mise en abyme⚓︎

La mise en abyme est un procédé consistant à représenter une œuvre dans une œuvre similaire, par exemple dans les phénomènes de « film dans un film », ou encore en incrustant dans une image cette image elle-même (en réduction). Ce principe se retrouve dans le phénomène ou le concept d'« autosimilarité », comme dans le principe des figures géométriques fractales ou du principe mathématique de la récursivité.

Mise en abyme simple

Cacao

La boite de conserve originale du cacao de la marque Droste, en 1904.

Crédits : Domaine public

Mise en abyme multiple

vache

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

IV. A vous de jouer⚓︎

Nous désirons créer une fonction qui trace ceci en utisant la bibliothèque turtle.
Il s'agit de triangles de Sierpiński.

triangles

Traçons un simple triangle.

Exécuter le code suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Votre figure

Votre tracé sera ici

Plusieurs triangle.

Utilisons une fonction récursive pour tracer plusieurs triangles.
Exécuter le code ci-dessous, et bien observer le résultat.

🐬 Pour voir la tortue se déplacer plus doucement, exécuter une deuxième fois ce code.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Votre figure

Votre tracé sera ici

Testons pour n = 2

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Votre figure

Votre tracé sera ici

Testons pour n = 3

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Votre figure

Votre tracé sera ici

Testons pour n = 4

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Votre figure

Votre tracé sera ici

Testons pour n = 5

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Votre figure

Votre tracé sera ici

Définition

Une fonction est dite récursive si elle contient un appel à elle-même dans sa propre définition.

Question 1

Que fait ce script ?

Python
def f_1():
    print("Bonjour")
    f_1()

f_1()
Solution

Ce script affiche "Bonjour" de nombreuses fois.

En théorie jusqu'à l'infini, mais Python arrête l'exécution au bout d'un moment et affiche un message d'erreur.

Question 2

Que fait ce script ?

Python
def f_2():
    f_2()
    print("Bonjour")

f_2()
Solution

Ce script n'affiche jamais "Bonjour", mais...

Il y a de nombreux appels récursifs, jusqu'au message d'erreur de Python

Question 3

Que fait ce script ?

Python
def f_3(n):
    print(n)
    if n > 0:
        f_3(n - 1)

f_3(4)
Solution

Tester :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Condition d'arrêt

Une fonction récursive étant une fonction qui s'appelle elle-même, on peut créer une fonction qui "tourne" théoriquement indéfiniment.

Python stoppe de lui même au bout d'un trop grand nombre d'appels de la fonction.

V. En informatique⚓︎

En informatique, on trouve :

  • des fonctions récursives, l'objet de ce chapitre ;
  • des structures de données récursives, comme une pile ou certains arbres, l'objet de chapitres suivants ;
  • des fractales ; nous apprendrons à en dessiner certaines.

le flocon de Koch

Le flocon de Koch est l'une des premières courbes fractales à avoir été décrites, bien avant l'invention du terme « fractal(e) » par Benoît Mandelbrot.

Koch

Elle a été inventée en 1904 par le mathématicien suédois Helge von Koch.

La fougère de Barnsley

La fougère de Barnsley est une fractale nommée d'après le mathématicien Michael Barnsley qui l'a décrite pour la première fois dans son livre Fractals Everywhere.

Fougère

L'arbre de Pythagore

L'arbre de Pythagore est une fractale plane construite à l'aide de carrés. Elle porte le nom de Pythagore car chaque triplet de carrés en contact enclot un triangle rectangle, une configuration traditionnellement utilisée pour illustrer le théorème de Pythagore.

Arbre Pythagore

V. Bilan⚓︎

Définition

Une fonction est dite récursive si elle contient un appel à elle-même dans sa propre définition.

Comment concevoir une fonction récursive

  1. Trouver le cas général : trouver l'élément de récursivité qui permet de décomposer le problème en cas plus simple.
  2. Trouver le cas de base : trouver la condition d'arrêt, et la solution du problème dans ce cas particulier.

    • La condition d'arrêt sera bien atteinte après un nombre fini d'appels.
    • Chaque appel récursif tend à s'approcher du cas de base.
  3. Réunir ces deux cas dans le programme :

    • Le programme ne contient aucune boucle (for ou while) dans la partie qui résoud le problème.
    • Le programme contient un général une structure if / else introduisant le cas de base.

VI. Crédits⚓︎

Franck Chambon