Aufgabe 03 - Rekursion I

Aufgabe 03 - Rekursion I

Worum geht es?

Sie schreiben Ihre ersten rekursiven Funktionen, verfolgen deren Aufrufketten von Hand und am Debugger und messen, was naive Rekursion kosten kann (siehe Kapitel Rekursion). Diese Übung legt das Fundament: Wer Basisfall, Rekursionsschritt und Call Stack hier sauber verstanden hat, löst die beiden Folgeübungen ohne Ratearbeit.

Was Sie dafür brauchen

• Kapitel Rekursion, Abschnitte Grundidee, Call Stack, Fakultät und Fibonacci.
• Python, VS Code mit Debugger.

Welche Kompetenzen Sie erwerben und zeigen

• Sie identifizieren und formulieren Basisfall und Rekursionsschritt einer rekursiven Funktion.
• Sie verfolgen Aufrufketten von Hand und mit dem Debugger und lesen den Call Stack.
• Sie vergleichen rekursive und iterative Lösungen anhand messbarer Kriterien.

Pädagogische Einordnung

• Reproduktion: die Begriffe Basisfall und Rekursionsschritt nennen, vorgegebene Muster nachvollziehen (Teil A).
• Reorganisation und Transfer: den Aufrufmechanismus auf neue Funktionen anwenden und visualisieren (Teile B und C).
• Reflexion, Problemlösung und Urteilsbildung: Laufzeitverhalten analysieren, eine Optimierung entwickeln und die Ergebnisse beurteilen (Teil D).

Arbeitsaufträge

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

Teil A - Aufwärmen

1. Tippen Sie countdown(n) aus dem Kapitel ab und führen Sie countdown(5) aus. Markieren Sie im Code mit zwei Kommentaren, welche Zeilen der Basisfall und welche der Rekursionsschritt sind.
2. Verschieben Sie die print-Zeile hinter den Selbstaufruf und führen Sie erneut aus. Beschreiben Sie in einem Satz, was sich geändert hat und warum.
3. Schreiben Sie sum_up_to(n) rekursiv (Summe 1 bis n). Kontrollwert: sum_up_to(100) ergibt 5050.

Teil B - Fakultät und Handrechnung

1. Implementieren Sie factorial(n) rekursiv.
2. Expandieren Sie factorial(4) schriftlich wie im Kapitel gezeigt: jede Zeile ein Auflösungsschritt, bis zum Zahlenwert 24. Diese Handrechnung ist Teil der Abgabe.
3. Setzen Sie einen Breakpoint in die Funktion und führen Sie factorial(4) im Debugger aus. Beobachten Sie das Call-Stack-Panel: Wie viele Einträge sehen Sie maximal, und welchen Wert hat n in jedem davon? Notieren Sie beides.

Teil C - Den Stack sichtbar machen

1. Ergänzen Sie factorial um einen Parameter depth=0 und rücken Sie jede Ausgabe mit " " * depth ein: beim Abstieg -> factorial(3), beim Aufstieg <- returns 6. Der Selbstaufruf übergibt depth + 1.
2. Rufen Sie factorial(-1) auf und provozieren Sie so den RecursionError. Lesen Sie die Fehlermeldung vollständig und erklären Sie in zwei Sätzen, warum der Basisfall hier nie erreicht wird.
3. Sichern Sie die Funktion ab: Für negative Eingaben gibt sie None zurück und druckt eine verständliche Meldung, statt abzustürzen.

Teil D - Expertenteil: Fibonacci und die Kosten

1. Implementieren Sie fib(n) rekursiv nach der Definition (fib(0) = 0, fib(1) = 1).
2. Bauen Sie einen Aufrufzähler ein (globale Variable oder Parameter) und füllen Sie eine Tabelle: Wie oft wird fib für n = 10, 20 und 30 insgesamt aufgerufen?
3. Schreiben Sie fib_memo(n) mit einem Dictionary als Gedächtnis (Memoisierung, siehe Kapitel) und wiederholen Sie die Zählung. Vergleichen Sie die beiden Tabellen.
4. Messen Sie mit time.perf_counter() die Laufzeit beider Varianten für n = 32 und dokumentieren Sie die Werte.
5. Formulieren Sie als Fazit in drei bis vier Sätzen: Was genau macht die naive Variante teuer, warum hilft das Gedächtnis, und was folgt daraus als Regel für eigene rekursive Funktionen?

Wissenscheck

1. Welche zwei Bestandteile braucht jede korrekte rekursive Funktion, und was garantiert jeder davon?
2. Warum gibt es beim Aufruf factorial(4) vier verschiedene Variablen n gleichzeitig?
3. Ein Programm bricht mit RecursionError: maximum recursion depth exceeded ab. Nennen Sie die zwei möglichen Ursachen aus dem Kapitel.
4. Warum zählt der countdown rückwärts, wenn print vor dem Selbstaufruf steht, und vorwärts, wenn es danach steht?
5. fib(30) braucht über eine Million Aufrufe, fib_memo(30) unter 60. Wo genau ist die Ersparnis?

Abgabe

recursion1.py mit allen Funktionen, die schriftliche Handrechnung aus Teil B (Foto oder Textdatei) und die Zähler- und Zeittabellen aus Teil D.