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 :

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.

Votre figure

Votre tracé sera ici

Testons pour n = 2

Votre figure

Votre tracé sera ici

Testons pour n = 3

Votre figure

Votre tracé sera ici

Testons pour n = 4

Votre figure

Votre tracé sera ici

Testons pour n = 5

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 ?

🐍 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 ?

🐍 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 ?

🐍 Script Python

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

f_3(4)

Solution

Tester :

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

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