Algorithmen und Komplexität · 2. Halbjahr

Rekursion

Die Schülerinnen und Schüler lösen Probleme durch den Selbstaufruf von Funktionen und verstehen die Funktionsweise von Rekursion.

Über dieses Thema

Rekursion ermöglicht es Schülerinnen und Schülern, komplexe Probleme durch den Selbstaufruf von Funktionen zu lösen. Sie lernen, Aufgaben wie die Berechnung der Fakultät oder das Durchlaufen von Bäumen in identische, kleinere Teilprobleme zu zerlegen. Der Basisfall stellt sicher, dass der Prozess endet, während rekursive Aufrufe die Lösung schrittweise aufbauen. Dies verbindet direkt mit den KMK-Standards STD.01 und STD.03 zu Algorithmen und Komplexität.

Im Kontext der Einheit 'Algorithmen und Komplexität' verstehen die Lernenden die Ablaufsteuerung: Jeder Aufruf erzeugt einen neuen Stackframe, was zu Stack Overflow führen kann, wenn die Rekursionstiefe zu groß wird. Sie analysieren, wann Rekursion iterativen Lösungen überlegen ist, etwa bei natürlichen rekursiven Strukturen wie Fraktalen oder Suchbäumen. Praktische Programmieraufgaben in Python oder einer Block-basierend Sprache festigen dieses Wissen.

Aktives Lernen eignet sich hervorragend für Rekursion, da abstrakte Konzepte durch Visualisierungen und Pair Programming konkret werden. Schülerinnen und Schüler modellieren Aufrufstapel mit Karten oder zeichnen Rekursionbäume, was Missverständnisse aufdeckt und tiefes Verständnis schafft. Solche Methoden machen den Selbstaufruf greifbar und motivieren zu experimentellem Programmieren.

Lernziele

• Analysieren Sie die Funktionsweise eines rekursiven Algorithmus anhand eines gegebenen Beispiels, indem Sie den Aufrufstapel Schritt für Schritt nachvollziehen.
• Entwerfen Sie eine rekursive Funktion zur Lösung eines einfachen Problems wie der Berechnung der Fakultät oder der Fibonacci-Folge.
• Vergleichen Sie eine gegebene rekursive Lösung mit einer äquivalenten iterativen Lösung hinsichtlich ihrer Lesbarkeit und potenziellen Effizienz.
• Bewerten Sie die Risiken eines Stack Overflows bei der Implementierung rekursiver Funktionen und schlagen Sie Strategien zur Vermeidung vor.
• Erklären Sie das Konzept des Basisfalls und seine Notwendigkeit für die Terminierung rekursiver Prozesse.

Bevor es losgeht

Grundlagen der Programmierung: Funktionen

Warum: Schülerinnen und Schüler müssen verstehen, wie Funktionen definiert, aufgerufen und mit Parametern übergeben werden, um das Konzept des Selbstaufrufs zu begreifen.

Kontrollstrukturen: Schleifen (Iteration)

Warum: Ein Vergleich zwischen Rekursion und Iteration ist erst sinnvoll möglich, wenn die Funktionsweise von Schleifen bekannt ist.

Schlüsselvokabular

Rekursion	Ein Verfahren, bei dem eine Funktion sich selbst aufruft, um ein Problem zu lösen, indem sie es in kleinere, identische Teilprobleme zerlegt.
Basisfall	Die Bedingung innerhalb einer rekursiven Funktion, die den rekursiven Aufruf beendet und somit einen Stack Overflow verhindert.
Rekursiver Aufruf	Der Aufruf derselben Funktion innerhalb ihres eigenen Körpers, der typischerweise mit modifizierten Parametern erfolgt, um dem Basisfall näher zu kommen.
Aufrufstapel (Call Stack)	Eine Datenstruktur, die die aktiven Funktionsaufrufe verwaltet; jeder rekursive Aufruf fügt einen neuen Eintrag hinzu, bis der Basisfall erreicht ist.
Stack Overflow	Ein Fehlerzustand, der auftritt, wenn der Aufrufstapel zu tief wird, weil zu viele rekursive Aufrufe ohne Erreichen des Basisfalls getätigt wurden.

Ideen für aktives Lernen

Pair Programming: Rekursive Fakultät

Paare implementieren eine rekursive Funktion zur Fakultätsberechnung in Python. Sie testen mit kleinen Werten, fügen den Basisfall ein und beobachten Ausgaben. Diskutieren Sie anschließend Iteration vs. Rekursion.

⏱ 30 Min.·Partnerarbeit

Mission erstellen

Small Groups: Rekursionsbaum visualisieren

Gruppen zeichnen den Aufrufbaum für Fibonacci-Zahlen bis n=5 auf Papier. Markieren Sie Basisfälle und Rückkehrwerte. Vergleichen Sie mit Code-Ausführung in einer IDE.

⏱ 25 Min.·Kleingruppen

Mission erstellen

Whole Class: Stack Overflow simulieren

Die Klasse simuliert rekursive Aufrufe mit Kartenstapeln: Jede Karte ist ein Frame. Fügen Sie Karten hinzu, bis der Stapel 'überläuft'. Diskutieren Sie Abhilfe durch Tail-Rekursion.

⏱ 35 Min.·Ganze Klasse

Mission erstellen

Individual: Fraktal zeichnen

Jede Schülerin und jeder Schüler programmiert eine einfache rekursive Turtle-Grafik, z. B. ein Sierpinski-Dreieck. Testen und modifizieren Sie Parameter für Tiefe.

⏱ 40 Min.·Einzelarbeit

Mission erstellen

Bezüge zur Lebenswelt

In der Computergrafik werden rekursive Algorithmen zur Erzeugung komplexer Fraktale wie der Mandelbrot-Menge oder zur Darstellung von Bäumen und Landschaften in Spielen und Simulationen verwendet. Entwickler bei Pixar nutzen solche Techniken, um realistische visuelle Effekte zu erzielen.

In der Informatik werden rekursive Ansätze häufig für das Durchlaufen von Baumstrukturen eingesetzt, beispielsweise in Datenbanken oder Dateisystemen. Systemadministratoren oder Softwareentwickler, die an der Organisation großer Datenmengen arbeiten, profitieren von diesem Verständnis, um effiziente Such- und Sortieralgorithmen zu entwickeln.

Bei der Analyse von Grammatiken und der Verarbeitung natürlicher Sprache können rekursive Muster helfen, verschachtelte Satzstrukturen zu erkennen. Linguisten und Entwickler von Sprachassistenten wie Siri oder Alexa verwenden diese Prinzipien, um die Struktur von Sätzen zu verstehen und korrekt zu interpretieren.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Rekursion führt immer zu unendlichen Schleifen.

Was Sie stattdessen lehren sollten

Der Basisfall verhindert das: Er stoppt Aufrufe bei kleinen Problemen. Pair Programming hilft, wo Schüler den Basisfall vergessen, da sie gegenseitig Code prüfen und Ausführungen debuggen.

Häufige Fehlvorstellung

Rekursion ist immer langsamer als Iteration.

Was Sie stattdessen lehren sollten

Bei Tail-Rekursion optimiert der Compiler zu Schleifen. Gruppenvisualisierungen zeigen, dass Rekursion bei Baumstrukturen natürlicher ist, und fördern Diskussionen über Komplexität.

Häufige Fehlvorstellung

Stack Overflow tritt nur bei sehr großen Eingaben auf.

Was Sie stattdessen lehren sollten

Es hängt von der Rekursionstiefe ab, nicht nur Größe. Stapel-Simulationen im Plenum machen dies spürbar und helfen, Grenzen früh zu erkennen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie jeder Schülerin und jedem Schüler eine kleine Karte. Bitten Sie sie, eine einfache rekursive Funktion (z.B. Fakultät) zu schreiben und den ersten rekursiven Aufruf sowie den Basisfall zu identifizieren. Notieren Sie auf der Rückseite, was passiert, wenn der Basisfall fehlt.

Kurze Überprüfung

Zeigen Sie eine kurze rekursive Funktion auf dem Beamer. Stellen Sie folgende Fragen: 'Welches Problem löst diese Funktion?', 'Was ist der Basisfall?', 'Was wäre der nächste rekursive Aufruf, wenn die Eingabe 5 wäre?'

Diskussionsfrage

Stellen Sie die Frage: 'In welchen Situationen wäre eine rekursive Lösung klarer und eleganter als eine iterative, und wann wäre das Gegenteil der Fall?' Lassen Sie die Schülerinnen und Schüler Beispiele aus ihren Programmierübungen oder bekannten Algorithmen anführen und begründen.

Häufig gestellte Fragen

Was ist Rekursion in der Informatik?

Rekursion ist eine Methode, bei der eine Funktion sich selbst aufruft, um ein Problem in kleinere identische Unterprobleme zu zerlegen. Ein Basisfall beendet den Prozess. Beispiele sind Fakultät (n! = n * (n-1)!) oder Fibonacci. Sie eignet sich für hierarchische Daten wie Bäume und trainiert strukturiertes Denken gemäß KMK-Standards.

Wie vermeidet man einen Stack Overflow bei Rekursion?

Definieren Sie klare Basisfälle und minimieren Sie die Rekursionstiefe, z. B. durch Tail-Rekursion oder Memoization. Testen Sie mit wachsenden Eingaben. Compiler-Optimierungen helfen bei tailrekursiven Funktionen. Praktische Simulationen lehren Schüler, Grenzen zu erkennen und iterative Alternativen zu entwickeln.

Wann ist Rekursion iterativen Lösungen überlegen?

Rekursion glänzt bei natürlichen rekursiven Strukturen wie Traversierungen von Bäumen, Fraktalen oder Divide-and-Conquer-Algorithmen wie QuickSort. Der Code wird eleganter und lesbarer. Iteration ist besser bei linearer Verarbeitung. Schüler lernen durch Vergleichsaufgaben, die richtige Wahl zu treffen.

Wie fördert aktives Lernen das Verständnis von Rekursion?

Aktive Methoden wie Pair Programming, Stapel-Visualisierungen mit Karten und rekursive Grafik-Experimente machen den unsichtbaren Aufrufprozess sichtbar. Schülerinnen und Schüler entdecken Basisfälle selbst, debuggen Fehler kollaborativ und vergleichen Rekursion mit Iteration. Das schafft tiefes, langlebiges Verständnis und reduziert Abstraktionsängste in 50-80 Wörtern.