comprendre ce qu'est la récursivité — une fonction qui s'appelle elle-même — sans tortue ni dessin.
Imagine que tu veux afficher 5, 4, 3, 2, 1, Décollage ! sans boucle for. La récursivité permet à une fonction de se répéter en se rappelant elle-même.
def compte_a_rebours(n):
if n == 0:
print("Décollage !")
else:
print(n)
compte_a_rebours(n - 1)
compte_a_rebours(5)
Recopie et exécute ce code depuis trinket. Que s'affiche-t-il ?
Quelle ligne est le cas de base (la condition qui arrête la récursion) ?
Que se passerait-il si on écrivait compte_a_rebours(-1) ? Essaie et observe.
Modifie la fonction pour qu'elle affiche les nombres dans l'ordre croissant (1, 2, 3… puis "Décollage !").
À retenir : toute fonction récursive a un cas de base (qui arrête) et un appel récursif (qui avance vers ce cas).
construire une récursivité avec deux appels récursifs et observer comment la nature utilise cette suite.
Rappel mathématique
La suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13, 21… Chaque terme est la somme des deux précédents. On trouve ces proportions dans les coquillages, les fleurs, les branches d'arbres — c'est une première forme de "fractal naturel".
def fibonacci(n):
if n == 1 or n == 2:
return 1
else:
return fibonacci(___) + fibonacci(___)
# Test
for i in range(1, 11):
print("F(" + str(i) + ") =", fibonacci(i))
Remplace les ___ pour que la fonction calcule correctement la suite.
Combien y a-t-il d'appels récursifs par appel de fibonacci ? Pourquoi est-ce différent de l'exercice 1 ?
Calcule fibonacci(10). Essaie fibonacci(35). Que remarques-tu sur le temps d'attente ?
Ajoute un compteur global pour compter combien de fois la fonction s'appelle pour fibonacci(10).
Lien fractal : les spirales de Fibonacci (phyllotaxie) sont un exemple de motif auto-similaire dans la nature : chaque sous-partie ressemble au tout.
dessiner un vrai fractal avec le module turtle disponible sur Basthon.
Une courbe de Von Koch se construit ainsi : divise un segment en 3 parties égales, remplace la partie centrale par un triangle équilatéral, répète sur chaque nouveau segment. À l'infini, on obtient un contour de longueur infinie qui délimite une aire finie.
import turtle
def von_koch(tortue, longueur, niveau):
if niveau == 0:
tortue.forward(longueur)
else:
von_koch(tortue, longueur / 3, niveau - 1)
tortue.left(60)
von_koch(tortue, longueur / 3, niveau - 1)
tortue.right(120)
von_koch(tortue, longueur / 3, niveau - 1)
tortue.left(60)
von_koch(tortue, longueur / 3, niveau - 1)
ecran = turtle.Screen()
t = turtle.Turtle()
t.speed(0)
t.penup()
t.goto(-150, 50)
t.pendown()
von_koch(t, 300, 3)
turtle.done()
Exécute avec niveau = 1, puis 2, puis 3. Décris la transformation entre chaque niveau.
Combien de segments droits contient la courbe pour le niveau 1 ? Le niveau 2 ? Le niveau 3 ? Donne la formule générale.
Modifie les angles (left et right) pour obtenir une variante différente. Que se passe-t-il si tu mets 90° à la place de 60° ?
Pour faire un flocon complet, répète la courbe 3 fois en ajoutant t.right(120) entre chaque côté. Code ce flocon entier.
Auto-similarité : chaque morceau du flocon de Von Koch est identique au flocon entier vu de plus près — c'est la définition d'un fractal.
dessiner un arbre dont chaque branche se subdivise en deux, comme dans la nature.
import turtle
def arbre(tortue, longueur, angle, reduction, niveau):
if niveau == 0:
return
tortue.forward(longueur)
tortue.left(angle)
arbre(tortue, longueur * reduction, angle, reduction, niveau - 1)
tortue.right(2 * angle)
arbre(tortue, longueur * reduction, angle, reduction, niveau - 1)
tortue.left(angle)
tortue.backward(longueur)
ecran = turtle.Screen()
t = turtle.Turtle()
t.speed(0)
t.left(90)
t.penup()
t.goto(0, -150)
t.pendown()
arbre(t, 80, 30, 0.7, 6)
turtle.done()
Exécute le code. Identifie dans la fonction les paramètres reduction et angle : que contrôlent-ils visuellement ?
Change reduction à 0.5 puis à 0.9. Compare les deux arbres obtenus. Lequel ressemble le plus à un vrai arbre ?
Ajoute une instruction pour que les branches deviennent vertes quand niveau <= 2 (feuilles) et marron sinon. Utilise tortue.pencolor(...).
Bonus : rends l'épaisseur du trait (tortue.pensize) proportionnelle au niveau : épaisse pour le tronc, fine pour les feuilles.
Retour en arrière : le tortue.backward(longueur) à la fin est crucial — il permet à la tortue de revenir au point de départ de la branche pour dessiner l'autre côté. C'est ce qu'on appelle le "backtracking" récursif.
implémenter un fractal célèbre en calculant les coordonnées des sous-triangles de manière récursive, sans tortue.
Le triangle de Sierpiński se construit en divisant un triangle en 4 sous-triangles et en supprimant le central. On répète l'opération sur les 3 triangles restants.
import turtle
def sierpinski(tortue, points, niveau):
if niveau == 0:
tortue.penup()
tortue.goto(points[0])
tortue.pendown()
for p in points[1:]:
tortue.goto(p)
tortue.goto(points[0])
else:
milieu = lambda a, b: ((a[0]+b[0])/2, (a[1]+b[1])/2)
m01 = milieu(points[0], points[1])
m12 = milieu(points[1], points[2])
m02 = milieu(points[0], points[2])
sierpinski(tortue, [points[0], m01, m02], niveau - 1)
sierpinski(tortue, [m01, points[1], m12], niveau - 1)
sierpinski(tortue, [m02, m12, points[2]], niveau - 1)
ecran = turtle.Screen()
t = turtle.Turtle()
t.speed(0)
t.hideturtle()
sommets = [(-150, -120), (150, -120), (0, 140)]
sierpinski(t, sommets, 4)
turtle.done()
Exécute avec niveau = 1, 2, 3, 4. Combien de triangles pleins sont dessinés à chaque niveau ?
Explique le rôle de la fonction milieu définie à l'intérieur de sierpinski. Pourquoi l'avoir écrite ainsi ?
Modifie le code pour colorier chaque sous-triangle selon son niveau de profondeur (utilise tortue.fillcolor et begin_fill / end_fill).
Défi final : calcule la proportion de l'aire du triangle initial encore "remplie" après chaque niveau. Quelle est la limite quand le niveau tend vers l'infini ? Qu'est-ce que cela nous dit sur les fractals ?