🧐 Qu’est-ce que la Récursivité ?

Imaginez un miroir face à un autre miroir… on voit des reflets de reflets, à l’infini ! La récursivité, c’est un peu ça en programmation. C’est quand une fonction s’appelle elle-même pour résoudre un problème. Ça peut sembler un peu bizarre au début, mais vous allez voir que c’est une idée géniale !

🏃‍♀️ Rappel : Les fonctions qui s’appellent !

Avant de parler de récursivité, rafraîchissons-nous la mémoire sur le fonctionnement des appels de fonctions.

Mini-Challenge 1 : Le Détective de Fonctions 🕵️‍♀️

Analysez et testez ce programme. Essayez de prédire l’ordre d’exécution !

Python

def reveil():
    print("Tic...")
    dodo()
    print("...Tac !")

def dodo():
    print("Zzzzz...")
    # Et si on appelait reveil() ici ? Essayez !
    print("...Mmmh !")

print("Journée qui commence !")
reveil()
print("Journée qui finit !")

Vous avez remarqué que quand reveil() appelle dodo(), l’exécution de reveil() se met en pause. C’est comme si reveil() disait : « Hé, dodo() ! Fais ton truc, et quand tu as fini, dis-le-moi pour que je reprenne ! ».

Pour gérer ça, Python (et la plupart des langages de programmation) utilise une pile d’exécution (ou « call stack »). C’est une sorte de pile de Post-it où chaque Post-it représente une fonction en cours d’exécution. La fonction au sommet est celle qui travaille, et celles en dessous attendent patiemment leur tour. Quand une fonction a fini, son Post-it est retiré du dessus de la pile.

C’est aussi grâce à cette pile que les variables locales à chaque fonction restent bien séparées. Le i de reveil() n’est pas le même que le i de dodo(), même s’ils ont le même nom ! C’est comme si chaque Post-it avait sa propre petite liste de courses.

😱 La Récursivité : Attention à la Boucle Infinie !

Maintenant, imaginez que notre fonction reveil() s’appelle elle-même !

Mini-Challenge 2 : La Cascade Infernale 🌊

Analysez et testez ce programme. Que se passe-t-il ? Pourquoi ?

Python

def chute_libre():
    print("Aïe !")
    chute_libre() # On s'appelle soi-même !

chute_libre()

Vous avez dû voir une erreur : RecursionError: maximum recursion depth exceeded. 🤯 C’est Python qui lève le drapeau rouge ! La pile d’exécution a grandi, grandi, grandi… sans jamais que les fonctions ne se terminent. C’est une boucle infinie récursive !

Pour qu’une fonction récursive soit utile, elle doit avoir une condition d’arrêt (ou « cas de base »). C’est le moment où la fonction ne s’appelle plus elle-même et renvoie une valeur. Sans ça, c’est le crash assuré !

🌟 La Magie de la Récursivité : Exemples Concrets

La récursivité est parfaite pour les problèmes qui peuvent être décomposés en sous-problèmes plus petits, mais de même nature.

🔢 L’Escalier Numérique 🪜

Imaginons que nous voulions afficher les nombres de 0 à n en partant de 0.

Mini-Challenge 3 : Prédiction et Vérification 🔮

Essayez de prévoir ce que va afficher le programme suivant. Puis, testez-le !

Python

def compte_a_rebours(n):
    if n < 0: # Notre condition d'arrêt !
        return
    print(n)
    compte_a_bours(n - 1)

compte_a_rebours(3)

Maintenant, si on voulait compter de 0 à n dans l’ordre croissant, il suffirait de changer l’ordre de print(n) et de l’appel récursif.

Python

def compte_en_avant(n):
    if n < 0:
        return
    compte_en_avant(n - 1)
    print(n) # L'affichage se fait après l'appel récursif !

compte_en_avant(3)

Remarquez la subtilité ! Dans compte_a_rebours, on affiche avant l’appel récursif, donc l’ordre est décroissant. Dans compte_en_avant, on affiche après l’appel récursif, donc l’ordre est croissant, car les print sont exécutés au moment où les fonctions sont « dépilées » de la pile ! C’est un point crucial à comprendre.

🎲 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 de manière récursive ?

1. On choisit un élément de la liste.
2. On permute le reste de la liste.
3. 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 : https://www.youtube.com/watch?v=F0vQnI20230 (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.

🚀 Étendre vos Horizons : Quand utiliser la Récursivité ?

La récursivité est un outil puissant, mais ce n’est pas toujours la meilleure solution.

Quand la récursivité brille ✨:

• Structures de données récursives : Arbres, listes chaînées… Parcourir ces structures est souvent très élégant avec la récursivité.
• Problèmes définis récursivement : La factorielle, la suite de Fibonacci, les tours de Hanoï, les fractales… La définition même du problème est récursive.
• Clarté du code : Pour certains problèmes, la solution récursive est plus courte et plus lisible que la solution itérative (avec des boucles).

Quand il faut être prudent ⚠️:

• Profondeur de récursion : Chaque appel récursif ajoute une « couche » sur la pile. Si la récursion est trop profonde (beaucoup d’appels successifs), vous risquez le RecursionError. Python a une limite par défaut (souvent autour de 1000 appels).
• Performance : Les appels de fonctions ont un coût. Parfois, une solution itérative est plus rapide et utilise moins de mémoire. La suite de Fibonacci est un bon exemple : la version récursive est très lente pour de grands nombres car elle recalcule les mêmes valeurs plusieurs fois.

💡 Un petit défi pour la route (pour plus tard) : Les Tours de Hanoï 🗼

Les Tours de Hanoï sont un puzzle classique parfait pour la récursivité. Vous avez 3 piquets et des disques de tailles différentes. Le but est de déplacer tous les disques d’un piquet de départ à un piquet d’arrivée, en ne déplaçant qu’un seul disque à la fois, et en ne posant jamais un grand 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.

J’espère que ce voyage au cœur de la récursivité vous a plu ! C’est un concept fondamental en informatique qui ouvre la porte à des solutions élégantes et à la compréhension de problèmes complexes. N’oubliez pas la règle d’or : une condition d’arrêt, toujours !

Alors, prêt à empiler les appels récursifs sans faire s’écrouler la pile ? 😉

Défi 1 : Le Compteur d’Étoiles Filantes 🌠

Imaginez que chaque nuit, le nombre d’étoiles filantes que vous voyez est le produit 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 multiplié par le nombre d’étoiles du jour n-1.

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 retourner 1.
• Cas récursif : compte_etoiles_filantes(n) doit retourner n * 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 (>= 0).
    Retourne (int): Le nombre cumulé d'étoiles.
    """
    if jour == 0:  # Cas de base : au jour 0, on a vu 1 étoile.
        return 1
    else:  # Cas récursif : le nombre d'étoiles du jour est n * (n-1) étoiles.
        return jour * compte_etoiles_filantes(jour - 1)

# Tests rapides :
print(f"Étoiles au jour 0 : {compte_etoiles_filantes(0)}")  # Attendu : 1
print(f"Étoiles au jour 1 : {compte_etoiles_filantes(1)}")  # Attendu : 1 (1 * 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 : 120 (5 * 4 * 3 * 2 * 1)

Défi 2 : La Danse des Fourmis de Syracuse 🐜

Imaginez une fourmi magicienne. Chaque jour, si son nombre de pattes est pair, elle en retire la moitié. Si son nombre de pattes est impair, elle se transforme en trois fourmis et gagne une patte supplémentaire (ce qui triple son nombre initial de pattes plus une). 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 la fourmi et affiche la séquence des nombres de pattes jour après jour, jusqu’à ce que la fourmi 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. Voir la Correction du Défi 2

Analyse du problème : La suite de Syracuse est définie par deux règles :

• Si u_n est pair : u_{n+1} = u_n / 2
• Si u_n est impair : u_{n+1} = 3 * u_n + 1 Le cas de base est lorsque u_n atteint 1.

Code :

Python

def danse_syracuse(nombre_pattes):
    """
    Affiche la séquence des nombres de pattes d'une fourmi de Syracuse.
    nombre_pattes (int): Le nombre de pattes actuel de la fourmi (doit être > 1).
    """
    print(nombre_pattes)  # On affiche le nombre de pattes actuel

    if nombre_pattes == 1:  # Cas de base : la fourmi 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 Mélodie des Nombres Étranges 🎶

Imaginez une mélodie où chaque note dépend des deux notes précédentes et d’une constante. La première note est toujours ‘A’ et la deuxième note est toujours ‘B’. Ensuite, chaque note est calculée en combinant trois fois la note précédente, deux fois l’avant-précédente, et en ajoutant cinq unités d’intensité.

Exercice : Écrivez une fonction récursive melodie_etrange(n, note_A, note_B) qui renvoie la valeur de la n-ième note de cette mélodie, 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. Voir la Correction du Défi 3

Analyse du problème : La suite est définie par :

• u_0 = a
• u_1 = b
• u_n = 3 * u_{n-1} + 2 * u_{n-2} + 5 pour n >= 2

Les cas de base sont n=0 et n=1. Pour les autres n, c’est un appel récursif.

Code :

Python

def melodie_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 * melodie_etrange(n - 1, note_A, note_B) + \
               2 * melodie_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=1, B=1): {melodie_etrange(2, 1, 1)}") # Attendu : 3*1 + 2*1 + 5 = 10
print(f"Mélodie à l'indice 3 (A=1, B=1): {melodie_etrange(3, 1, 1)}") # u2=10, u1=1. Attendu : 3*10 + 2*1 + 5 = 37

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 (rien n'est affiché) :")
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 (%). Voir la Correction du Défi 5

Analyse du problème : L’algorithme d’Euclide est intrinsèquement récursif :

• Cas de base : Si b est 0, le PGCD est a.
• 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.

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. Voir la Correction du Défi 6

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 n plus grand, le nombre de chiffres est 1 (pour le chiffre des unités) plus le nombre de chiffres de n // 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 n est 0, il n’y a aucun bit 1.
• Pour n > 0, on vérifie le dernier bit (n % 2). S’il vaut 1, on l’ajoute au compte. Ensuite, on compte les bits 1 dans 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_depart atteint la fin du tableau (len(tableau)), cela signifie que la valeur n’a pas été trouvée, donc on retourne False.
• Cas de base 2 : Si la valeur à tableau[indice_depart] correspond à valeur, on a trouvé, on retourne True.
• 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 :

1. É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.
2. Utilisez une double boucle for pour 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 est 1.
• Cas de base 2 : n = p, le coefficient est 1.
• 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 : L’Art du Flocon Mystérieux de Koch ❄️

Plongez dans le monde des fractales ! Le flocon de Koch est une figure envoûtante qui se construit en ajoutant des triangles à des segments. Chaque segment de la figure se transforme en une version plus petite de la figure elle-même.

Exercice : En utilisant le module turtle, écrivez une fonction récursive dessine_flocon_koch(profondeur, longueur) qui dessine un flocon de Koch d’une certaine profondeur de récursion, à partir d’un segment initial de longueur.

Prérequis : Maîtrise des bases du module turtle (déplacements, rotations). Compréhension de la description géométrique du flocon de Koch. Voir la Correction du Défi 10

Analyse du problème : Le flocon de Koch est construit à partir de trois courbes de Koch de même longueur, tournées de 120 degrés. La courbe de Koch elle-même est récursive :

• Cas de base : Si profondeur est 0, on dessine simplement un segment.
• Cas récursif : On remplace un segment par 4 segments plus petits (longueur / 3), avec des rotations.

Code :

Python

import turtle as t

# Configuration initiale de Turtle
t.speed(0) # Vitesse maximale pour un dessin rapide
t.penup()
t.goto(-200, 100) # Position de départ pour centrer le flocon
t.pendown()
t.color("lightblue") # Couleur du flocon
t.pensize(2) # Épaisseur du trait

def courbe_koch(profondeur, longueur):
    """
    Dessine une courbe de Koch de profondeur donnée.
    profondeur (int): Le niveau de récursion (0 pour un segment droit).
    longueur (float): La longueur du segment initial.
    """
    if profondeur == 0:
        t.forward(longueur)
    else:
        # Chaque segment est remplacé par 4 segments plus petits,
        # formant une "bosse" au milieu.
        courbe_koch(profondeur - 1, longueur / 3)
        t.left(60)
        courbe_koch(profondeur - 1, longueur / 3)
        t.right(120)
        courbe_koch(profondeur - 1, longueur / 3)
        t.left(60)
        courbe_koch(profondeur - 1, longueur / 3)

def dessine_flocon_koch(profondeur, longueur):
    """
    Dessine un flocon de Koch complet.
    profondeur (int): Le niveau de récursion du flocon.
    longueur (float): La longueur de chaque côté du triangle initial.
    """
    for _ in range(3): # Un flocon est composé de 3 courbes de Koch
        courbe_koch(profondeur, longueur)
        t.right(120) # Tourner pour dessiner le côté suivant du triangle

# Tests rapides :
# Dessiner un flocon avec 3 niveaux de profondeur et des côtés de 300 unités
dessine_flocon_koch(3, 300)

t.done() # Garde la fenêtre Turtle ouverte jusqu'à fermeture manuelle

Alors, ces défis vous ont-ils fait voir la récursivité sous un nouveau jour ? La récursivité est un outil puissant et élégant quand il est bien utilisé. N’hésitez pas à rejouer ces défis avec différentes valeurs pour bien comprendre comment la pile d’exécution travaille ! Quelle est votre fractale préférée à part celle de Koch ?