Rekursive Algorithmen

2.1 Durchlaufen eines Dateibaums

Lass uns einen rekursiven Algorithmus betrachten, um einen Dateibaum zu durchlaufen. Der Algorithmus wird ein Verzeichnis und alle seine Unterverzeichnisse durchlaufen und eine Liste aller Dateien und Ordner ausgeben.

import os

def list_files_recursive(directory, indent=0):
    # Erhalte eine Liste aller Dateien und Ordner im aktuellen Verzeichnis
    items = os.listdir(directory)
                
    for item in items:
        # Erstelle den vollständigen Pfad zur Datei oder zum Ordner
        path = os.path.join(directory, item)
                    
        # Gib mit Einrückung aus, um die Struktur besser zu verstehen
        print(' ' * indent + item)
                    
        # Wenn es ein Ordner ist, durchlaufe rekursiv dessen Inhalt
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Beispiel für die Verwendung
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Wie funktioniert das?

1. Funktion list_files_recursive(directory, indent=0):
   • directory — das aktuelle Verzeichnis, dessen Inhalt wir anzeigen möchten.
   • indent — die aktuelle Einrückungsebene, um die Verschachtelung von Dateien und Ordnern anzuzeigen.
2. Erhalte eine Liste aller Dateien und Ordner im aktuellen Verzeichnis mit os.listdir(directory).
3. Durchlaufe jedes Element in der Liste items.
4. Erstelle den vollständigen Pfad zum Element mit os.path.join(directory, item).
5. Gib den Namen des Elements mit Einrückung aus, die um 4 Leerzeichen für jede Verschachtelungsebene zunimmt.
6. Überprüfe, ob das Element ein Ordner ist mit os.path.isdir(path). Wenn ja, rufe list_files_recursive(path, indent + 4) rekursiv auf, um dessen Inhalt zu durchlaufen.

Beispielausgabe:

Angenommen, wir haben die folgende Verzeichnisstruktur:

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

Beim Ausführen der Funktion list_files_recursive(root_directory) erhalten wir folgende Ausgabe:

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

Dieser Algorithmus durchläuft rekursiv den Verzeichnisbaum und gibt alle Dateien und Ordner unter Berücksichtigung ihrer Verschachtelung aus.

2.2 Türme von Hanoi

Das Problem der „Türme von Hanoi“

Türme von Hanoi ist ein klassisches rekursives Problem, das das Verschieben von Scheiben von einem Stab auf einen anderen mithilfe eines Hilfsstabs beinhaltet.

Regeln:

1. Man darf immer nur eine Scheibe auf einmal verschieben.
2. Eine Scheibe kann nur auf einen leeren Stab oder auf eine größere Scheibe gelegt werden.
3. Alle Scheiben müssen von einem Stab auf einen anderen verschoben werden, indem man den Hilfsstab nutzt.

Hier ist der rekursive Algorithmus zur Lösung dieses Problems:

Der Algorithmus der Türme von Hanoi löst das Problem folgendermaßen:

1. Verschiebe n - 1 Scheiben vom Ausgangsstab auf den Hilfsstab, indem du den Zielstab verwendest.
2. Verschiebe die verbleibende Scheibe vom Ausgangsstab auf den Zielstab.
3. Verschiebe n - 1 Scheiben vom Hilfsstab auf den Zielstab, indem du den Ausgangsstab verwendest.

Beispiel in Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Verschiebe Scheibe 1 von {source} nach {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Verschiebe Scheibe {n} von {source} nach {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Beispiel für die Verwendung:
n = 3  # Anzahl der Scheiben
hanoi_tower(n, 'A', 'C', 'B')
        

Wie funktioniert das?

Basisfall:

Wenn es nur eine Scheibe gibt (n == 1), kann diese einfach vom Ausgangsstab auf den Zielstab verschoben werden.

if n == 1:
    print(f"Verschiebe Scheibe 1 von {source} nach {target}")
    return

Rekursiver Fall:

Schritt 1. Verschiebe n-1 Scheiben vom Ausgangsstab auf den Hilfsstab, indem du den Zielstab verwendest.

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

Schritt 2. Verschiebe die Scheibe n vom Ausgangsstab auf den Zielstab.

print(f"Verschiebe Scheibe {n} von {source} nach {target}")

Schritt 3. Verschiebe n - 1 Scheiben vom Hilfsstab auf den Zielstab, indem du den Ausgangsstab verwendest.

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

Beispielausgabe:

Für drei Scheiben (n = 3) auf den Stäben A, B und C, gibt das Programm aus:

Verschiebe Scheibe 1 von A nach C
Verschiebe Scheibe 2 von A nach B
Verschiebe Scheibe 1 von C nach B
Verschiebe Scheibe 3 von A nach C
Verschiebe Scheibe 1 von B nach A
Verschiebe Scheibe 2 von B nach C
Verschiebe Scheibe 1 von A nach C

2.3 Knochenschneeflocke

Das Zeichnen einer Schneeflocke mit Rekursion ist eine interessante Aufgabe, die oft verwendet wird, um Fraktale zu studieren. Eine einfache Möglichkeit, eine Schneeflocke zu zeichnen, ist die Verwendung der Knochenskurve, die eine fraktale Kurve darstellt.

Algorithmus zum Zeichnen der Knochenschneeflocke

Die Knochenskurve wird folgendermaßen konstruiert:

• Beginne mit einer geraden Linie.
• Teile jedes Segment in drei Teile und ersetze den mittleren Teil durch eine kleine Kurve, die einem „Knick“ ähnelt.
• Wiederhole diesen Prozess rekursiv für jedes Segment.

Schritt-für-Schritt-Anleitung

• Anfang: Zeichne das Anfangssegment.
• Aufteilen: Teile jedes Segment in drei Teile.
• Ersetze den mittleren Teil: Zeichne auf dem mittleren Teil einen „Knick“, der aus zwei Linien besteht, die einen Winkel von 60 Grad bilden.
• Wiederhole den Prozess: Setze diesen Prozess für jedes Segment fort.

Beispiel in Python mit der Bibliothek 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)
            
# Bildschirm-Einstellungen
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Turtle-Einstellungen
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Zeichne die Schneeflocke
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Beende das Zeichnen
turtle.done()
            

Wie funktioniert das?

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

• t: die Turtle, die zeichnet.
• length: die Länge des Segments.
• depth: die Rekursionstiefe, die das Detailgrad bestimmt.

2. Basisfall:

Wenn depth gleich 0 ist, zeichnet die Turtle ein gerades Segment.

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

3. Rekursiver Fall:

Teile das Segment in drei Teile und wende draw_koch_curve rekursiv auf jeden Teil an, füge Drehungen hinzu.

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. Funktion draw_snowflake(t, length, depth):

Zeichnet drei Knochenskurven, die zu einer Schneeflocke verbunden sind.

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

Wie führe ich den Code aus?

• Stelle sicher, dass die Bibliothek Turtle (pip install PythonTurtle) installiert ist.
• Kopiere und füge den Code in eine .py-Datei ein und führe ihn aus. Du wirst die Schneeflockenzeichnung auf dem Bildschirm sehen.

Dieser Algorithmus ermöglicht es, die fraktale Struktur der Schneeflocke mit einfachen Prinzipien der Rekursion und geometrischen Konstruktionen zu visualisieren.