Algorithmes récursifs

2.1 Parcours d'arborescence de fichiers

Regardons un algorithme récursif pour parcourir une arborescence de fichiers. L'algorithme parcourra un répertoire et tous ses sous-répertoires, affichant la liste de tous les fichiers et dossiers.

import os

def list_files_recursive(directory, indent=0):
    # Obtenir la liste de tous les fichiers et dossiers dans le répertoire courant
    items = os.listdir(directory)
                
    for item in items:
        # Créer le chemin complet vers le fichier ou le dossier
        path = os.path.join(directory, item)
                    
        # Afficher avec un retrait pour mieux percevoir la structure
        print(' ' * indent + item)
                    
        # Si c'est un dossier, parcourir son contenu récursivement
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Exemple d'utilisation
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Comment ça fonctionne ?

1. Fonction list_files_recursive(directory, indent=0):
   • directory — répertoire courant dont nous voulons afficher le contenu.
   • indent — niveau actuel de retrait, pour montrer l'imbrication des fichiers et dossiers.
2. Obtenir la liste de tous les fichiers et dossiers dans le répertoire courant avec os.listdir(directory).
3. Passer en revue chaque élément dans la liste items.
4. Créer le chemin complet vers l'élément avec os.path.join(directory, item).
5. Afficher le nom de l'élément avec un retrait qui augmente de 4 espaces pour chaque niveau d'imbrication.
6. Vérifier si l'élément est un dossier avec os.path.isdir(path). Si oui, appeler récursivement list_files_recursive(path, indent + 4) pour parcourir son contenu.

Exemple de sortie :

Supposons que nous ayons la structure de répertoires suivante :

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

En appelant la fonction list_files_recursive(root_directory), nous obtiendrons la sortie suivante :

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

Cet algorithme parcourt récursivement l'arborescence des répertoires, affichant tous les fichiers et dossiers avec leur imbrication.

2.2 Tours de Hanoï

Problème des « Tours de Hanoï »

Les Tours de Hanoï sont un problème classique de récursion qui implique de déplacer des disques d'une tige à une autre en utilisant une tige auxiliaire.

Règles :

1. On ne peut déplacer qu'un seul disque à la fois.
2. Un disque peut être placé uniquement sur une tige vide ou sur un disque de plus grande taille.
3. Il faut déplacer tous les disques d'une tige à une autre en utilisant la tige auxiliaire.

Voici un algorithme récursif pour résoudre ce problème :

L'algorithme des Tours de Hanoï résout le problème de la manière suivante :

1. Déplacer n - 1 disques de la tige de départ vers l'auxiliaire, en utilisant la tige cible.
2. Déplacer le disque restant de la tige de départ à la tige cible.
3. Déplacer n - 1 disques de la tige auxiliaire à la tige cible, en utilisant la tige de départ.

Exemple en Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Déplacer le disque 1 de {source} à {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Déplacer le disque {n} de {source} à {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Exemple d'utilisation :
n = 3  # Nombre de disques
hanoi_tower(n, 'A', 'C', 'B')
        

Comment ça fonctionne ?

Cas de base :

S'il n'y a qu'un disque (n == 1), on peut simplement le déplacer de la tige de départ à la tige cible.

if n == 1:
    print(f"Déplacer le disque 1 de {source} à {target}")
    return

Cas récursif :

Étape 1. Déplacer les n-1 disques de la tige de départ vers l'auxiliaire, en utilisant la tige cible.

hanoi_tower(n - 1, source, auxiliary, target)

Étape 2. Déplacer le disque n de la tige de départ à la tige cible.

print(f"Déplacer le disque {n} de {source} à {target}")

Étape 3. Déplacer les n - 1 disques de la tige auxiliaire à la tige cible, en utilisant la tige de départ.

hanoi_tower(n - 1, auxiliary, target, source)

Exemple de sortie :

Pour trois disques (n = 3) sur les tiges A, B et C, le programme affichera :

Déplacer le disque 1 de A à C
Déplacer le disque 2 de A à B
Déplacer le disque 1 de C à B
Déplacer le disque 3 de A à C
Déplacer le disque 1 de B à A
Déplacer le disque 2 de B à C
Déplacer le disque 1 de A à C

2.3 Flocon de Koch

Dessiner un flocon de neige à l'aide de la récursion est une tâche intéressante, souvent utilisée pour étudier les fractals. Une des manières simples de dessiner un flocon est d'utiliser la courbe de Koch, qui est une courbe fractale.

Algorithme pour dessiner un flocon de Koch

La courbe de Koch se construit de la manière suivante :

• Commencer avec une ligne droite.
• Diviser chaque segment en trois parties et remplacer la partie centrale par une petite courbe, ressemblant à un "angle".
• Répéter ce processus de manière récursive pour chaque segment.

Instructions étape par étape

• Début : Dessinez le segment initial.
• Division : Divisez chaque segment en trois parties.
• Remplacer la partie centrale : Sur la partie centrale, dessinez un "angle", constitué de deux lignes formant un angle de 60 degrés.
• Répétez le processus : Continuez ce processus pour chaque segment.

Exemple en Python avec la bibliothèque Turtle

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# Configuration de l'écran
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Configuration de la tortue
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Dessiner le flocon
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Terminer le dessin
turtle.done()
            

Comment ça fonctionne ?

1. Fonction draw_koch_curve(t, length, depth):

• t : la tortue qui dessine.
• length : longueur du segment.
• depth : profondeur de récursion, déterminant le niveau de détail.

2. Cas de base :

Si depth est égal à 0, la tortue dessine un segment droit.

if depth == 0:
    t.forward(length)
        

3. Cas récursif :

Diviser le segment en trois parties, et appliquer draw_koch_curve récursivement à chaque partie, en ajoutant des rotations.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. Fonction draw_snowflake(t, length, depth):

Elle dessine trois courbes de Koch, connectées pour former un flocon de neige.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

Comment exécuter le code ?

• Assurez-vous que la bibliothèque Turtle est installée (pip install PythonTurtle).
• Copiez et collez le code dans un fichier .py et exécutez-le. Vous verrez le flocon se dessiner à l'écran.

Cet algorithme permet de visualiser la structure fractale d'un flocon en utilisant des principes simples de récursion et de constructions géométriques.