1. Compte à rebours - ma première fonction récursive

Objectif : 

comprendre ce qu'est la récursivité — une fonction qui s'appelle elle-même — sans tortue ni dessin.

Mise en situation

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.

Code de départ

def compte_a_rebours(n):
    if n == 0:
        print("Décollage !")
    else:
        print(n)
        compte_a_rebours(n - 1)

compte_a_rebours(5)

1. Recopie et exécute ce code depuis trinket. Que s'affiche-t-il ?

2. Quelle ligne est le cas de base (la condition qui arrête la récursion) ?

3. Que se passerait-il si on écrivait compte_a_rebours(-1) ? Essaie et observe.

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

2. La suite de Fibonacci - récursivité et motifs répétitifs

Objectif : 

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

Code à compléter

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

1. Remplace les ___ pour que la fonction calcule correctement la suite.

2. Combien y a-t-il d'appels récursifs par appel de fibonacci ? Pourquoi est-ce différent de l'exercice 1 ?

3. Calcule fibonacci(10). Essaie fibonacci(35). Que remarques-tu sur le temps d'attente ?

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

3. Le flocon de Von Koch - tortue et récursivité

Objectif : 

dessiner un vrai fractal avec le module turtle disponible sur Basthon.

Principe de construction

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.

Code

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()

1. Exécute avec niveau = 1, puis 2, puis 3. Décris la transformation entre chaque niveau.

2. Combien de segments droits contient la courbe pour le niveau 1 ? Le niveau 2 ? Le niveau 3 ? Donne la formule générale.

3. 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° ?

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

4. L'arbre fractal - branches récursives

Objectif : 

dessiner un arbre dont chaque branche se subdivise en deux, comme dans la nature.

Code

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()

1. Exécute le code. Identifie dans la fonction les paramètres reduction et angle : que contrôlent-ils visuellement ?

2. Change reduction à 0.5 puis à 0.9. Compare les deux arbres obtenus. Lequel ressemble le plus à un vrai arbre ?

3. Ajoute une instruction pour que les branches deviennent vertes quand niveau <= 2 (feuilles) et marron sinon. Utilise tortue.pencolor(...).

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

5. Le triangle de Sierpinsky - fractals et récursivité pure

Objectif : 

implémenter un fractal célèbre en calculant les coordonnées des sous-triangles de manière récursive, sans tortue.

Approche par coordonnées

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()

1. Exécute avec niveau = 1, 2, 3, 4. Combien de triangles pleins sont dessinés à chaque niveau ?

2. Explique le rôle de la fonction milieu définie à l'intérieur de sierpinski. Pourquoi l'avoir écrite ainsi ?

3. Modifie le code pour colorier chaque sous-triangle selon son niveau de profondeur (utilise tortue.fillcolor et begin_fill / end_fill).

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