Aufgabe 04 - Rekursion II

Aufgabe 04 - Rekursion II

Worum geht es?

Rekursion zeigt ihre Stärke bei verschachtelten Strukturen: Sie verarbeiten beliebig tief verschachtelte Listen, durchwandern echte Verzeichnisbäume und lösen mit den Türmen von Hanoi das Paradebeispiel rekursiver Problemzerlegung (siehe Kapitel Rekursion). Am Ende können Sie die Anwendungsgebiete der Rekursion benennen und belegen, eine ausdrückliche Lehrplan-Kompetenz.

Was Sie dafür brauchen

• Kapitel Rekursion, Abschnitte Datenstrukturen, Grenzen und Türme von Hanoi.
• Aufgabe 03 (Basisfall und Rekursionsschritt sitzen).
• Python, VS Code; für Teil C einen eigenen Übungsordner mit einigen Unterordnern und Dateien.

Welche Kompetenzen Sie erwerben und zeigen

• Sie verarbeiten rekursive Datenstrukturen mit strukturell passenden rekursiven Funktionen.
• Sie setzen pathlib für Dateisystemoperationen ein.
• Sie erkennen und benennen reale Anwendungsgebiete der Rekursion.

Pädagogische Einordnung

• Reproduktion: vorgegebenen rekursiven Code nachvollziehen und sein Verhalten beschreiben (Teil A).
• Reorganisation und Transfer: das Muster der Strukturrekursion auf Listen und Verzeichnisse übertragen (Teile B und C).
• Reflexion, Problemlösung und Urteilsbildung: ein anspruchsvolles Problem rekursiv zerlegen, Gesetzmäßigkeiten herleiten und Anwendungsgebiete beurteilen (Teil D).

Arbeitsaufträge

Die Übung ist auf etwa zwei Stunden ausgelegt. Teil D ist der Expertenteil.

Teil A - Lesen und Verstehen

Gegeben ist die Funktion aus dem Kapitel:

def total_duration(entries):
    total = 0
    for entry in entries:
        if isinstance(entry, list):
            total += total_duration(entry)
        else:
            total += entry
    return total

1. Bestimmen Sie ohne Ausführen das Ergebnis für [1, [2, 3], [4, [5]]]. Kontrollieren Sie danach am Rechner.
2. Wo versteckt sich hier der Basisfall? (Vorsicht, er steht in keiner eigenen if-Zeile.) Antwort in einem Satz.
3. Ändern Sie die Funktion zu count_numbers(entries): Sie zählt, wie viele Zahlen die Struktur enthält, statt sie zu summieren.

Teil B - Verschachtelte Listen selbst

Schreiben Sie die folgenden Funktionen selbst. Beide arbeiten auf beliebig tief verschachtelten Listen von Zahlen und müssen rekursiv gelöst werden. Testen Sie jede Funktion mit mindestens drei Beispielstrukturen, darunter eine flache und eine mindestens dreifach verschachtelte.

1. max_depth(entries): liefert die maximale Verschachtelungstiefe ([1, [2, [3]]] ergibt 3, [1, 2] ergibt 1, [] ergibt 1).
2. deep_max(entries): liefert die größte Zahl der gesamten Struktur. Entscheiden und dokumentieren Sie, was bei einer leeren Struktur passiert.
3. Erklären Sie in zwei Sätzen, warum eine einfache Schleife ohne Rekursion bei diesen Aufgaben unvorteilhaft ist.

Teil C - Verzeichnisbaum

Legen Sie einen eigenen Übungsordner mit mehreren Unterordnern und Dateien an. Schreiben Sie darauf aufbauend die folgenden Funktionen mit pathlib; ein Verzeichnisbaum ist eine rekursive Struktur, ein Ordner enthält wieder Ordner.

1. show_tree(folder, depth=0): gibt einen echten Ordner mit pathlib rekursiv als eingerückten Baum aus, Unterordner zuerst, dann Dateien.
2. total_size(folder): liefert die Gesamtgröße aller Dateien unterhalb des Ordners in Bytes (entry.stat().st_size).
3. find_files(folder, extension): liefert eine Liste aller Dateien mit der angegebenen Endung, egal wie tief sie liegen.
4. Testen Sie alle drei Funktionen an Ihrem Übungsordner, nicht an Systemverzeichnissen.

Teil D - Expertenteil: Türme von Hanoi

Lösen Sie die folgenden vier Punkte in dieser Reihenfolge: erst selbst implementieren, dann messen, dann die Gesetzmäßigkeit herleiten und beurteilen.

1. Implementieren Sie hanoi(n, source, target, spare) mit Zugausgaben (disk 1: A -> C), bevor Sie die Kapitel-Lösung noch einmal ansehen. Halten Sie vorher schriftlich in zwei Sätzen die rekursive Zerlegung fest (“Um n Scheiben zu bewegen, …”).
2. Zählen Sie die Züge für n = 3, 5 und 10 mit. Leiten Sie aus den drei Werten die allgemeine Formel für die Zugzahl her und begründen Sie sie kurz (Blick auf die Struktur der Funktion: zwei Selbstaufrufe plus ein Zug).
3. Lassen Sie Python ausrechnen, wie viele Jahre 64 Scheiben bei einem Zug pro Sekunde dauern. Ordnen Sie das Ergebnis in einem Satz ein: Was bedeutet exponentielles Wachstum praktisch?
4. Nennen Sie abschließend vier reale Anwendungsgebiete der Rekursion mit je einem Halbsatz Begründung. Mindestens zwei davon sollen aus dieser Übung stammen.

Wissenscheck

1. Woran erkennen Sie einer Datenstruktur an, dass sie nach einer rekursiven Verarbeitung verlangt?
2. Warum braucht show_tree keinen explizit hingeschriebenen Basisfall?
3. Was prüft isinstance(entry, list), und warum ist diese Prüfung in total_duration unverzichtbar?
4. Die Zugzahl bei Hanoi wächst mit 2ⁿ - 1. Was passiert mit der Rechendauer, wenn eine Scheibe dazukommt?
5. Nennen Sie zwei rekursive Strukturen, mit denen Sie außerhalb des Programmierens täglich zu tun haben.

Abgabe

recursion2.py mit allen Teilen; die Herleitung der Zugformel und die Anwendungsgebiete-Liste als Kommentar am Dateiende.