La Récursivité

🧐 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_rebours(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.

Amusons nous avec les suites , tout de suite

une bonne partie des suites vues en cours de mathématiques sont des suites définies par récurrence, elle se prêtent particulièrement bien à une utilisation des fonctions récursives. Nous allons nous intéresser à une suite définie de la manière suivante : u_{0}=5 et : u_{n+1} = 3/4*u_{n} + 11.

On peut accéder assez facilement à n’importe quel terme à l’aide d’une boucle.

n=int(input("quel terme voulez vous ? "))
u = 5
for i in range(1,n+1) :
     u = 3/4*u + 11
print(f"le {n}ième terme est {u}")

mais un tel programme n’a pas vraiment de rapport avec le cœur du chapitre, on peut raisonner à l’envers en exprimant u_4 à partir de u_3 qui lui sera exprimé à partir de u_2 etc

def u(n):
    if n == 0 : return 5
    return 3/4*u(n-1) + 11

n=int(input("quel terme voulez vous ? "))

print(f"le {n}ième terme est {u(n)}")

la récurrence est en quelque sorte tournée vers l’arrière, le présent est une fonction du passé.

Il y a moyen d’aller de l’avant, mais avec les suites qui sont infinies ça peut durer longtemps. On a besoin de trouver un point d’arrêt futur.

Imaginons que pour la suite précédente on ait remarqué que la suite converge vers 44, et que l’on ait envie de savoir quand est ce que l’on arrive à une distance epsilon de cette limite.

def verif(epsilon,n=0,u=5):
    #print("début de l'appel n°",n) # juste pour arriver à mieux comprendre ce qui se joue
    if abs(u-44)<epsilon :
         print("on y arrive pour n =",n)
         return
    verif(epsilon,n+1,3/4*u+11)
    #print("début de l'appel n°",n) # juste pour arriver à mieux comprendre ce qui se joue

verif(0.01)

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

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

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.

correction

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

fin du cours

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

Imaginez que l’on décide de regarder les étoiles filante chaque nuit à partir d’une première nuit . chaque nuit, le nombre d’étoiles filantes que vous voyez est exactement égal au numéro du jour, autrement dit la cinquième nuit on verra 5 étoiles filantes.

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 1, vous avez vu 1 étoile filante. Pour tout jour n > 1, le nombre d’étoiles est n s’ajoute au nombre d’étoiles des jour n-1 jusqu’à 1.

Prérequis : Maîtrise des concepts de base des fonctions (définition, appel, return).

Analyse du problème : La définition nous est donnée :

• Cas de base : compte_etoiles_filantes(1) doit retourner 1.
• Cas récursif : compte_etoiles_filantes(n) doit retourner n + compte_etoiles_filantes(n-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 )

correction

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

correction

Défi 3 : La Mélodie 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 = 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.

# 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

correction

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

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.

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

correction

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 b est 0, le PGCD est a.
• Cas récursif : Sinon, PGCD(a, b) = PGCD(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

correction

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 n plus grand, le nombre de chiffres est 1 (pour le chiffre des unités) plus le nombre de chiffres de 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

correction

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

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

# 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

correction

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.

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

# 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

correction

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.

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

# 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

correction

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()
                                     #dessiner le triangle orienté vers le haut
    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
        # faire trois appels au rang n-1 , avec une dimension diminuée et commençant au bon endroit

def SierCent(l,c1,c2,n) : #petit bonus pour faire partir la figure à partir d'un point optimal
    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 *

speed(0) # Vitesse maximale pour un dessin rapide

def rectangle(x,y,h,l,c):


def Sierpinsky(x,y,h,l,c1,c2,n):
    if n==0 :
        
    else :
        #faire 8 appels de la fonction Sierpinski au rang n-1 et un rectangle de couleur c2
        Sierpinsky(x,y,h/3,l/3,c1,c2,n-1)
        ...

Sierpinsky(-200,200,400,400,"blue","red",4)
done() # Garde la fenêtre ouverte

🎲 Le Maître des Permutations 🤹‍♂️ un défis qui vous mettra à rude épreuve

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 peut visualiser ça avec un arbre de combinaisons (même principe qu’un arbre de probabilités)

1. On choisit un élément de la liste.
2. On identifie ce qui reste d’éléments à traiter
3. Et après cet élément on aura toutes les permutations des éléments restants. 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.
4. On combine l’élément choisi avec toutes les permutations du reste.
5. retour au 1. jusqu’à ce qu’on finisse de couvrir les éléments de la liste

Les Arrangements de Mots ✍️

En vous inspirant de ce qui précède, essayez de compléter cette fonction pour qu’elle affiche toutes les permutations d’une chaîne de caractères (par exemple, « ABC »).

def permuter(chaine):
    if                   : #condition d'arrêt
        return [chaine]
    
    permutations = []
    for i, char in enumerate(chaine): #pour chaque caractère choisi on a une double info : son rang et le caractère lui même
        reste =                       # Le reste de la chaîne , il faudra se rappeler comment prendre des morceaux 
                                      #d'une chaine et les concaténer
                                                          
        # 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:
                                                   #on rajoute à notre liste "permutations" une chaine 
                                                   #formée de la lettre choisie et de la combinaison du moment
            
    return permutations  #on renvoie une liste de permutation des éléments restants passés en paramètre dans "permuter"

print(permuter("ABC"))

correction

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 !

💡 Un petit défi pour la route : 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.

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.

correction

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 ?