🎲 Le Maître des Permutations 🤹♂️
Un problème classique et élégant à résoudre avec la récursivité est de générer toutes les permutations d’une liste (toutes les façons d’ordonner ses éléments).
Par exemple, pour [1, 2, 3], les permutations sont [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
Comment ça marche pour trouver les permutation des éléments d’une liste
- On choisit un élément de la liste.
- On identifie ce qui reste d’éléments à traiter
- On lance un appel de notre fonction récursive pour générer une liste des permutations de ce qui reste d’éléments à traiter (autrement dit on crée un liste des permutations des éléments restants) cet appel peut en provoquer un autre qui en provoque un autre…jusqu’à ce que le reste ne contienne qu’un élément et dans ce cas la liste renvoyée est très courte, elle ne contient qu’un élément le fameux élément restant.
- On combine l’élément choisi avec toutes les permutations du reste.
Mini-Application 1 : Les Arrangements de Mots ✍️
Essayez de compléter cette fonction pour qu’elle affiche toutes les permutations d’une chaîne de caractères (par exemple, « ABC »).
Python
def permuter(chaine):
if len(chaine) == 1:
return [chaine]
permutations = []
for i, char in enumerate(chaine):
# On choisit un caractère
reste = chaine[:i] + chaine[i+1:] # Le reste de la chaîne
# On permute le reste
permutations_restantes = permuter(reste)
# On combine le caractère choisi avec les permutations du reste
for p_reste in permutations_restantes:
permutations.append(char + p_reste)
return permutations
print(permuter("ABC"))
C’est un peu plus complexe, mais ça montre bien la puissance de la récursivité pour découper un gros problème en petits morceaux !
🎨 La Beauté des Fractales avec Turtle 🐢
La récursivité est la reine des fractales, ces formes géométriques complexes qui se répètent à l’infini à différentes échelles. Le flocon de Koch est un exemple magnifique.
Mini-Challenge 4 : Le Flocon Magique ❄️
Regardez cette vidéo sur le flocon de Koch (ou cherchez « flocon de Koch animation » si le lien ne marche pas).
Ensuite, analysez et testez le code suivant. Concentrez-vous sur les paramètres longueur et n (le nombre d’étapes de récursivité).
Python
import turtle as t
t.speed(0) # Vitesse maximale pour un dessin rapide
t.penup()
t.goto(-150, 90) # Position de départ pour que le flocon soit bien centré
t.pendown()
def koch(longueur, n):
if n == 0:
t.forward(longueur)
else:
# Chaque segment est remplacé par 4 segments plus petits
koch(longueur / 3, n - 1)
t.left(60)
koch(longueur / 3, n - 1)
t.right(120)
koch(longueur / 3, n - 1)
t.left(60)
koch(longueur / 3, n - 1)
def flocon(taille, etape):
for _ in range(3): # Un flocon est composé de 3 segments de Koch
koch(taille, etape)
t.right(120)
flocon(300, 4) # Essayez différentes valeurs pour taille et etape !
t.done() # Garde la fenêtre ouverte
Le secret du flocon de Koch réside dans la fonction koch : si n est 0, on dessine juste un segment droit. Sinon, on remplace ce segment par 4 segments plus petits, en tournant de 60 ou 120 degrés, et on appelle koch récursivement pour chacun de ces segments ! C’est le principe des fractales : une petite partie ressemble au tout.
Fin du cours
Défi 1 : Le Compteur d’Étoiles Filantes 🌠
Imaginez que chaque nuit, le nombre d’étoiles filantes que vous voyez est la somme du nombre d’étoiles vues la veille, la veille de la veille, etc., jusqu’à la première nuit où vous n’en avez vu qu’une seule !
Exercice : Créez une fonction récursive nommée compte_etoiles_filantes(jour) qui calcule le nombre cumulé d’étoiles filantes observées jusqu’à un certain jour. Par définition, au jour 0, vous avez vu 1 étoile filante. Pour tout jour n > 0, le nombre d’étoiles est n s’ajoute au nombre d’étoiles des jour n-1 jusqu’à 0.
Prérequis : Maîtrise des concepts de base des fonctions (définition, appel, return). Voir la Correction du Défi 1
Analyse du problème : La définition nous est donnée :
- Cas de base :
compte_etoiles_filantes(0)doit retourner1. - Cas récursif :
compte_etoiles_filantes(n)doit retournern + compte_etoiles_filantes(n-1).
Code :
Python
def compte_etoiles_filantes(jour):
"""
Calcule le nombre cumulé d'étoiles filantes jusqu'à un certain jour.
jour (int): Le numéro du jour (>= 1).
Retourne (int): Le nombre cumulé d'étoiles.
"""
if jour == 1: # Cas de base : au jour 1, on a vu 1 étoile.
return 1
else: # Cas récursif : le nombre d'étoiles jusqu'au jour n est (n + le nombre d'étoiles vues jusqu'au jour n-1).
return jour + compte_etoiles_filantes(jour - 1)
# Tests rapides :
print(f"Étoiles au jour 1 : {compte_etoiles_filantes(2)}") # Attendu : 3 (2 + 1)
print(f"Étoiles au jour 3 : {compte_etoiles_filantes(3)}") # Attendu : 6 (3 + 2 + 1)
print(f"Étoiles au jour 5 : {compte_etoiles_filantes(5)}") # Attendu : 15 (5 + 4 + 3 + 2 + 1 )
Défi 2 : La Danse des insectes de Syracuse 🐜
Imaginez un insecte magicien. Chaque jour, si son nombre de pattes est pair, il en perd la moitié. Si son nombre de pattes est impair, son nombre de pattes triple et gagne une patte supplémentaire en prime. La légende dit que toutes les fourmis finissent toujours par n’avoir qu’une seule patte.
Exercice : Écrivez une fonction récursive danse_syracuse(nombre_pattes) qui prend en paramètre le nombre de pattes initial de l’insecte et affiche la séquence des nombres de pattes jour après jour, jusqu’à ce que l’insecte n’en ait plus qu’une. On supposera nombre_pattes est un entier positif strictement supérieur à 1.
Prérequis : Maîtrise des opérateurs modulo (%) et division entière (//). Comprendre l’importance du cas de base pour éviter la récursion infinie.
Analyse du problème : La suite de Syracuse est définie par deux règles :
- Si
u_nest pair :u_{n+1} = u_n / 2 - Si
u_nest impair :u_{n+1} = 3 * u_{n} + 1Le cas de base est lorsqueu_{n]atteint1.
Code :
Python
def danse_syracuse(nombre_pattes):
"""
Affiche la séquence des nombres de pattes d'un insecte de Syracuse.
nombre_pattes (int): Le nombre de pattes actuel de l'insecte (doit être > 1).
"""
print(nombre_pattes) # On affiche le nombre de pattes actuel
if nombre_pattes == 1: # Cas de base : l'insecte n'a plus qu'une patte
return
if nombre_pattes % 2 == 0: # Si le nombre de pattes est pair
danse_syracuse(nombre_pattes // 2)
else: # Si le nombre de pattes est impair
danse_syracuse(3 * nombre_pattes + 1)
# Tests rapides :
print("Séquence pour 6 :")
danse_syracuse(6)
# Attendu : 6 3 10 5 16 8 4 2 1
print("\nSéquence pour 27 :")
danse_syracuse(27)
# La séquence est plus longue, mais doit finir par 1.
Défi 3 : La suite des Nombres Étranges 🎶
Imaginez une suite où chaque valeur dépend des deux valeurs précédentes et d’une constante. La première valeur est notée ‘A’ et la deuxième note est notée ‘B’. Ensuite, chaque nouvelle note est calculée en combinant trois fois la note précédente, deux fois celle d’avant et en ajoutant cinq .
Exercice : Écrivez une fonction récursive suite_etrange(n, note_A, note_B) qui renvoie la valeur de la n-ième note de cette suite, en considérant que n=0 correspond à note_A et n=1 à note_B.
Prérequis : Compréhension des suites définies par récurrence sur plusieurs termes précédents.
Analyse du problème : La suite est définie par :
u_0 = au_1 = bu_n = 3 * u_{n-1} + 2 * u_{n-2} + 5pourn >= 2
Les cas de base sont n=0 et n=1. Pour les autres n, c’est un appel récursif.
Code :
Python
def suite_etrange(n, note_A, note_B):
"""
Renvoie le n-ième terme d'une suite récursive avec deux cas de base.
n (int): L'indice du terme à calculer (>= 0).
note_A (float/int): La valeur du terme u_0.
note_B (float/int): La valeur du terme u_1.
Retourne (float/int): Le n-ième terme de la suite.
"""
if n == 0: # Premier cas de base
return note_A
elif n == 1: # Deuxième cas de base
return note_B
else: # Cas récursif
return 3 * suite_etrange(n - 1, note_A, note_B) + 2 * suite_etrange(n - 2, note_A, note_B) + 5
# Tests rapides :
print(f"Mélodie à l'indice 0 (A=10, B=20): {melodie_etrange(0, 10, 20)}") # Attendu : 10
print(f"Mélodie à l'indice 1 (A=10, B=20): {melodie_etrange(1, 10, 20)}") # Attendu : 20
print(f"Mélodie à l'indice 2 (A=10, B=20): {melodie_etrange(2, 10, 20)}") # Attendu : 3*20 + 2*10 + 5 = 85
print(f"Mélodie à l'indice 3 (A=10, B=20): {melodie_etrange(3, 10, 20)}") # Attendu : 3*85 + 2*20 + 5 = 300
Défi 4 : Le Labyrinthe des Chiffres Croissants 🔢➡️🔢
Imaginez que vous êtes dans un labyrinthe où chaque pièce est un chiffre. Vous ne pouvez avancer que vers des pièces avec un chiffre plus élevé, et vous voulez visiter toutes les pièces entre un point de départ et un point d’arrivée.
Exercice : Créez une fonction récursive explore_labyrinthe(depart, arrivee) qui affiche tous les entiers de depart à arrivee (inclus), dans l’ordre croissant.
Prérequis : Maîtrise des opérateurs de comparaison et des structures conditionnelles (if). Voir la Correction du Défi 4
Analyse du problème : Le cas de base est lorsque depart dépasse arrivee. Sinon, on affiche depart et on explore le reste du labyrinthe en augmentant depart.
Code :
Python
def explore_labyrinthe(depart, arrivee):
"""
Affiche tous les entiers entre depart et arrivee (inclus) dans l'ordre.
depart (int): L'entier de départ.
arrivee (int): L'entier d'arrivée.
"""
if depart > arrivee: # Cas de base : on a dépassé l'arrivée
return
else: # Cas récursif
print(depart, end=" ") # Afficher l'entier actuel
explore_labyrinthe(depart + 1, arrivee) # Appeler la fonction pour l'entier suivant
# Tests rapides :
print("Exploration de 0 à 3 :")
explore_labyrinthe(0, 3) # Attendu : 0 1 2 3
print("\nExploration de 5 à 5 :")
explore_labyrinthe(5, 5) # Attendu : 5
print("\nExploration de 7 à 4 :")
explore_labyrinthe(7, 4) # Attendu : rien (condition depart > arrivee est vraie immédiatement)
Défi 5 : Le Décodeur de Clés Secrètes (PGCD) 🔑
Pour déverrouiller une porte secrète, vous avez besoin du plus grand commun diviseur (PGCD) de deux nombres. La machine utilise un algorithme où si le deuxième nombre est zéro, le PGCD est le premier nombre. Sinon, le PGCD est celui du deuxième nombre et du reste de la division du premier par le deuxième.
Exercice : Écrivez une fonction récursive decode_cle_secrete(a, b) qui renvoie le PGCD de deux entiers positifs a et b, en utilisant l’algorithme d’Euclide.
Prérequis : Connaissance de l’algorithme d’Euclide pour le PGCD, et de l’opérateur modulo (%).
Analyse du problème : L’algorithme d’Euclide est intrinsèquement récursif : on fait des divisions euclidiennes successives et à chaque fois le diviseur devient le nouveau dividende et le reste devient le nouveau diviseur. Du coup le PGCD de la paire de base a la même valeur que la paire suivante, qui aura la même valeur que … De plus on est censé s’arrêter et prendre le dernier reste non nul. Vérifier que tout ça peut être traduit de la manière suivante :
- Cas de base : Si
best0, le PGCD esta. - Cas récursif : Sinon,
PGCD(a, b) = PGCD(b, a % b).
Code :
Python
def decode_cle_secrete(a, b):
"""
Calcule le Plus Grand Commun Diviseur (PGCD) de deux entiers positifs.
a (int): Le premier entier.
b (int): Le deuxième entier.
Retourne (int): Le PGCD de a et b.
"""
if b == 0: # Cas de base de l'algorithme d'Euclide
return a
else: # Cas récursif
return decode_cle_secrete(b, a % b)
# Tests rapides :
print(f"PGCD(48, 18) : {decode_cle_secrete(48, 18)}") # Attendu : 6
print(f"PGCD(17, 5) : {decode_cle_secrete(17, 5)}") # Attendu : 1
print(f"PGCD(100, 25) : {decode_cle_secrete(100, 25)}") # Attendu : 25
print(f"PGCD(7, 0) : {decode_cle_secrete(7, 0)}") # Attendu : 7
Défi 6 : L’Inspecteur de Chiffres 🕵️♀️
Vous êtes un inspecteur et vous devez compter le nombre de chiffres qui composent un suspect numérique. Chaque fois que vous examinez un chiffre, vous retirez ce chiffre et comptez le reste. Par exemple si vous inspectez 179, vous allez prendre 9, et il restera 17, puis vous prendrez 7, il restera 1, vous le prenez il ne reste rien. Vous avez pris successivement trois chiffres avant de ne rien avoir à prendre donc, la réponse vous allez rendre/afficher est 3. Ça à l’air simple comme ça, mais passer de 179 à 17 puis à 1 et enfin à rien, ça va vous demander un peu de réflexion.
Exercice : Écrivez une fonction récursive inspecteur_de_chiffres(n) qui prend un entier positif ou nul n et renvoie son nombre de chiffres décimaux.
Prérequis : Maîtrise des opérateurs de division entière (//). Gérer le cas n=0 correctement.
Analyse du problème :
- Le nombre de chiffres d’un nombre entre 0 et 9 est 1. C’est notre cas de base.
- Pour un nombre
nplus grand, le nombre de chiffres est1(pour le chiffre des unités) plus le nombre de chiffres den // 10.
Code :
Python
def inspecteur_de_chiffres(n):
"""
Renvoie le nombre de chiffres décimaux d'un entier positif ou nul.
n (int): L'entier à analyser (>= 0).
Retourne (int): Le nombre de chiffres.
"""
if n < 10: # Cas de base : si n est un chiffre (0-9)
return 1
else: # Cas récursif : retirer le dernier chiffre et compter le reste
return 1 + inspecteur_de_chiffres(n // 10)
# Tests rapides :
print(f"Chiffres de 0 : {inspecteur_de_chiffres(0)}") # Attendu : 1
print(f"Chiffres de 7 : {inspecteur_de_chiffres(7)}") # Attendu : 1
print(f"Chiffres de 42 : {inspecteur_de_chiffres(42)}") # Attendu : 2
print(f"Chiffres de 12345 : {inspecteur_de_chiffres(12345)}") # Attendu : 5
Défi 7 : Le Compteur de Bits Lumineux 💡
Dans le monde binaire, certains bits sont « lumineux » (valent 1) et d’autres sont « éteints » (valent 0). Vous devez compter combien de bits lumineux il y a dans la représentation binaire d’un nombre.
Exercice : Écrivez une fonction récursive compteur_bits_lumineux(n) qui prend un entier positif ou nul n et renvoie le nombre de bits valant 1 dans sa représentation binaire.
Prérequis : Connaissance des opérateurs binaires (% 2 pour le dernier bit, // 2 pour décaler à droite). Voir la Correction du Défi 7
Analyse du problème :
- Le cas de base est lorsque
nest0, il n’y a aucun bit1. - Pour
n > 0, on vérifie le dernier bit (n % 2). S’il vaut 1, on l’ajoute au compte. Ensuite, on compte les bits1dans le reste du nombre (n // 2).
Code :
Python
def compteur_bits_lumineux(n):
"""
Renvoie le nombre de bits valant 1 dans la représentation binaire d'un entier.
n (int): L'entier positif ou nul.
Retourne (int): Le nombre de bits à 1.
"""
if n == 0: # Cas de base : plus de bits à examiner
return 0
else: # Cas récursif
# On ajoute 1 si le dernier bit est 1 (n % 2)
# Puis on compte les bits 1 dans le reste du nombre (n // 2)
return (n % 2) + compteur_bits_lumineux(n // 2)
# Tests rapides :
print(f"Bits lumineux de 0 (0b0) : {compteur_bits_lumineux(0)}") # Attendu : 0
print(f"Bits lumineux de 1 (0b1) : {compteur_bits_lumineux(1)}") # Attendu : 1
print(f"Bits lumineux de 2 (0b10) : {compteur_bits_lumineux(2)}") # Attendu : 1
print(f"Bits lumineux de 3 (0b11) : {compteur_bits_lumineux(3)}") # Attendu : 2
print(f"Bits lumineux de 255 (0b11111111) : {compteur_bits_lumineux(255)}") # Attendu : 8
print(f"Bits lumineux de 10 (0b1010) : {compteur_bits_lumineux(10)}") # Attendu : 2
Défi 8 : Le Détecteur d’Intrusions dans le Tableau 🚨
Vous êtes le gardien d’un tableau de valeurs et vous devez vérifier si une valeur spécifique est présente à partir d’un certain point.
Exercice : Écrivez une fonction récursive detecteur_intrusions(valeur, tableau, indice_depart) qui renvoie True si valeur apparaît dans tableau à partir de indice_depart (inclus) jusqu’à la fin du tableau, et False sinon. On garantit que indice_depart est toujours un indice valide.
Prérequis : Maîtrise des listes/tableaux (accès par indice, len()), des opérateurs de comparaison et des booléens. Voir la Correction du Défi 8
Analyse du problème :
- Cas de base 1 : Si
indice_departatteint la fin du tableau (len(tableau)), cela signifie que la valeur n’a pas été trouvée, donc on retourneFalse. - Cas de base 2 : Si la valeur à
tableau[indice_depart]correspond àvaleur, on a trouvé, on retourneTrue. - Cas récursif : Sinon, on continue la recherche à l’indice suivant (
indice_depart + 1).
Code :
Python
def detecteur_intrusions(valeur, tableau, indice_depart):
"""
Vérifie si une valeur est présente dans un tableau à partir d'un certain indice.
valeur (any): La valeur à rechercher.
tableau (list): Le tableau dans lequel chercher.
indice_depart (int): L'indice à partir duquel commencer la recherche (inclus, >=0).
Retourne (bool): True si la valeur est trouvée, False sinon.
"""
# Cas de base 1 : L'indice a dépassé la fin du tableau, la valeur n'est pas trouvée.
if indice_depart == len(tableau):
return False
# Cas de base 2 : La valeur est trouvée à l'indice actuel.
elif tableau[indice_depart] == valeur:
return True
# Cas récursif : La valeur n'est pas à l'indice actuel, on cherche dans le reste du tableau.
else:
return detecteur_intrusions(valeur, tableau, indice_depart + 1)
# Tests rapides :
mon_tableau = [10, 20, 30, 40, 50]
print(f"20 dans [10, 20, 30, 40, 50] à partir de 0 : {detecteur_intrusions(20, mon_tableau, 0)}") # Attendu : True
print(f"60 dans [10, 20, 30, 40, 50] à partir de 0 : {detecteur_intrusions(60, mon_tableau, 0)}") # Attendu : False
print(f"40 dans [10, 20, 30, 40, 50] à partir de 3 : {detecteur_intrusions(40, mon_tableau, 3)}") # Attendu : True
print(f"10 dans [10, 20, 30, 40, 50] à partir de 1 : {detecteur_intrusions(10, mon_tableau, 1)}") # Attendu : False
print(f"50 dans [10, 20, 30, 40, 50] à partir de 4 : {detecteur_intrusions(50, mon_tableau, 4)}") # Attendu : True
Défi 9 : Le Secret du Triangle Magique de Pascal 🧙♂️
Le triangle de Pascal est un artefact mathématique où chaque nombre est la somme des deux nombres directement au-dessus de lui. Les bords du triangle sont toujours des 1.
Exercice :
- Écrivez une fonction récursive
coefficient_magique(n, p)qui renvoie la valeur du coefficient binomial C(n,p) (le nombre à la ligne n et à la position p dans le triangle de Pascal), en utilisant la définition récursive donnée :- C(n,p)=1 si p=0 ou n=p
- C(n,p)=C(n−1,p−1)+C(n−1,p) sinon.
- Utilisez une double boucle
forpour afficher les 11 premières lignes (de n=0 à n=10) du triangle de Pascal, en utilisant votre fonction.
Prérequis : Maîtrise des boucles for imbriquées et de l’affichage formaté (print). Comprendre la définition mathématique récursive. Voir la Correction du Défi 9
Analyse du problème : La définition récursive est très claire :
- Cas de base 1 :
p = 0, le coefficient est1. - Cas de base 2 :
n = p, le coefficient est1. - Cas récursif :
C(n-1, p-1) + C(n-1, p).
Code :
Python
def coefficient_magique(n, p):
"""
Calcule le coefficient binomial C(n, p) du triangle de Pascal de manière récursive.
n (int): Le numéro de la ligne (>= 0).
p (int): La position dans la ligne (0 <= p <= n).
Retourne (int): La valeur du coefficient C(n, p).
"""
if p == 0 or n == p: # Cas de base : les bords du triangle
return 1
else: # Cas récursif : somme des deux éléments au-dessus
return coefficient_magique(n - 1, p - 1) + coefficient_magique(n - 1, p)
# Tests rapides de la fonction :
print(f"C(0, 0) : {coefficient_magique(0, 0)}") # Attendu : 1
print(f"C(3, 1) : {coefficient_magique(3, 1)}") # Attendu : 3
print(f"C(4, 2) : {coefficient_magique(4, 2)}") # Attendu : 6
# Dessin du triangle de Pascal
print("\n--- Triangle Magique de Pascal (jusqu'à n=10) ---")
for n_ligne in range(11): # Pour chaque ligne de 0 à 10
# Optionnel : pour centrer l'affichage (ajuster selon la taille de la console)
print(" " * (10 - n_ligne), end="")
for p_position in range(n_ligne + 1): # Pour chaque position dans la ligne
print(f"{coefficient_magique(n_ligne, p_position):4d}", end="") # :4d pour aligner
print() # Passer à la ligne suivante
Défi 10 : Retour sur les autres fractales
Faites une petite recherche sur les fractales de Sierpinsky.
Est ce que l’image fournie par l’IA est réaliste ? Etudier d’un peu plus près la logique derrière les deux fractales.
Exercice :
Créer deux programmes pour les deux versions de la fractale
Analyse du problème et conseils : on peut créer une fonction dessinant le motif de base : un triangle équilatéral / rectangle.
les coordonnées d’un triangle équilatéral de côté l et dont le premier sommet a pour coordonnées (0,0) seront (0,0) , (l,0) et (l/2,racine(3)/2).
pour le triangle de Sierpinski voici un début de programme :
from turtle import *
from math import sqrt
speed(0) # Vitesse maximale pour un dessin rapide
def triangle(x:int,y:int,l:int,c:str):
"""dessine un triangle équilatéral de dimension l et de couleur c
il aura une base horizontale et la pointe vers le haut"""
penup()
goto(x,y) # Position de départ pour le rectangle
pendown()
fillcolor(c)
begin_fill()
forward(l)
left(120)
forward(l)
left(120)
forward(l)
left(120)
end_fill()
def SierTri(x,y,l,c1,c2,n):
"""dessine le triangle de Sierpinski de dimension l à l'ordre n,
son premier sommet a pour coordonnées (x,y), c1 est la couleur majoritaire
c2 est celle des incrustations"""
if n==0 :
triangle(x,y,l,c1)
else :
triangle(x,y,l,c2) #l'incrustation apparaitra par transparence
SierTri(x,y,l/2,c1,c2,n-1)
SierTri(x+l/2,y,l/2,c1,c2,n-1)
SierTri(x+l/4,y+sqrt(3)*l/4,l/2,c1,c2,n-1)
def SierCent(l,c1,c2,n) :
SierTri(-l/2,-sqrt(3)*l/4,l,c1,c2,n)
SierCent(200,"blue","red",4)
done() # Garde la fenêtre ouverte
- Pour le tapis, un peu moins d’aide est nécessaire,
from turtle import *
def rectangle(x,y,h,l,c):
penup()
goto(x,y) # Position de départ pour le rectangle
pendown()
fillcolor(c)
begin_fill()
forward(l)
right(90)
forward(h)
right(90)
forward(l)
right(90)
forward(h)
right(90)
end_fill()
def Sierpinsky(x,y,h,l,c1,c2,n):
if n==0 :
rectangle(x,y,h,l,c1)
else :
Sierpinsky(x,y,h/3,l/3,c1,c2,n-1)
Sierpinsky(x+l/3,y,h/3,l/3,c1,c2,n-1)
Sierpinsky(x+2*l/3,y,h/3,l/3,c1,c2,n-1)
Sierpinsky(x,y-h/3,h/3,l/3,c1,c2,n-1)
rectangle(x+l/3,y-h/3,h/3,l/3,c2)
Sierpinsky(x+2*l/3,y-h/3,h/3,l/3,c1,c2,n-1)
Sierpinsky(x,y-2*h/3,h/3,l/3,c1,c2,n-1)
Sierpinsky(x+l/3,y-2*h/3,h/3,l/3,c1,c2,n-1)
Sierpinsky(x+2*l/3,y-2*h/3,h/3,l/3,c1,c2,n-1)
speed(0) # Vitesse maximale pour un dessin rapide
Sierpinsky(-200,200,400,400,"blue","red",4)
done() # Garde la fenêtre ouverte
🚀 Étendre vos Horizons : Quand utiliser la Récursivité ?
disque sur un petit.
Mini-Application 2 : Le Déplaceur de Disques 💿
Recherchez les « Tours de Hanoï algorithme récursif » et essayez d’implémenter une fonction Python qui affiche les étapes pour déplacer les disques.
Python
def hanoi(n, source, cible, auxiliaire):
if n == 1:
print(f"Déplacer le disque 1 de {source} vers {cible}")
else:
hanoi(n - 1, source, auxiliaire, cible)
print(f"Déplacer le disque {n} de {source} vers {cible}")
hanoi(n - 1, auxiliaire, cible, source)
# Exemple : résoudre pour 3 disques
hanoi(3, "A", "C", "B")