Rekursion im Informatikunterricht

Aspekt	Befund	Planning use
Lehrplaninhalt	Rekursiver Aufruf, Abbruchbedingung, lineare und verzweigte Rekursion	Diese Begriffe als Gerüst der Unterrichtsreihe nutzen und nacheinander einführen.
Kompetenz	Rekursive Algorithmen analysieren und das Prinzip der Rekursion erläutern	Schüler müssen Aufrufe nachverfolgen und erklären, nicht nur Code abschreiben.
Vergleich	Iterative und rekursive Algorithmen für geeignete Problemstellungen vergleichen	Zu jeder Rekursionsaufgabe die Schleifenvariante mitdenken, wo sie sinnvoll existiert.
Türme von Hanoi	Rekursive Lösung über Teilprobleme; zusätzlich ein iterativer Lösungsalgorithmus ohne Rekursion	Hanoi als Beispiel für Zerlegung einsetzen, nicht als Beleg dafür, dass Rekursion unverzichtbar ist.
Java-Umsetzung	Ein Java-Programm gibt die Züge aus; die Scheibenzahl kann beim Programmstart übergeben werden	Als Programmieraufgabe nach dem Verständnis auf Papier einplanen.

Die Angaben stützen sich auf die Beschreibung des Lernbereichs Rekursion im LehrplanPLUS G9 Informatik und auf die Hanoi-Seite des Programmierkurses der Universität Düsseldorf.

Stichwort rekursion informatik schule: Eine rekursive Methode ruft sich selbst mit einem kleineren Teilproblem auf und endet an einer Abbruchbedingung. Entscheidend ist, dass Schüler diesen Ablauf nachvollziehen, bevor sie ihn programmieren.

Den größeren Zusammenhang zeigt der Überblick zum informatikunterricht oberstufe. Passende Aufgabenblätter und Vorlagen finden sich im unterrichtsmaterial informatik oberstufe.

Folgen für die Unterrichtsplanung

Der Lehrplan verlangt beim Thema Rekursion mehr als das Schreiben einer Methode. Laut LehrplanPLUS G9 Informatik sollen Schüler rekursive Algorithmen analysieren und das Prinzip der Rekursion erläutern. Das verschiebt den Schwerpunkt vom Programmieren zum Verstehen und Erklären.

• Begriffe zuerst festlegen: Rekursiver Aufruf, Abbruchbedingung sowie lineare und verzweigte Rekursion stehen im Lehrplan als Inhalte. Wer sie früh sauber benennt, kann in jeder späteren Aufgabe darauf zurückgreifen.
• Nachvollziehen vor Schreiben: Weil die Kompetenz mit „analysieren“ beginnt, lohnen sich Aufgaben, in denen ein fertiger rekursiver Code gelesen und erklärt wird. Eigene Implementierungen folgen danach.
• Vergleich einplanen: Der Lehrplan nennt den Vergleich iterativer und rekursiver Algorithmen ausdrücklich. Eine Rekursionsreihe ohne diesen Schritt bleibt deshalb unvollständig.
• Zeit nicht unterschätzen: Das Thema bildet im Lehrplan einen eigenen Lernbereich. Es sollte daher nicht als Nebenbemerkung zwischen anderen Themen auftauchen.

Rekursion oder Schleife: Entscheidungshilfe

Eine pauschale Antwort, wann Rekursion besser als eine Schleife ist, gibt der Lehrplan nicht. Er spricht von „geeigneten Problemstellungen“. Die Eignung ergibt sich aus der Struktur des Problems.

• Rekursion passt, wenn sich ein großes Problem auf kleinere, einfacher lösbare Teilprobleme gleicher Art zurückführen lässt. Die Düsseldorfer Hanoi-Seite beschreibt genau dieses Vorgehen und zieht den Vergleich zu Mergesort.
• Eine Schleife passt, wenn derselbe Schritt einfach der Reihe nach wiederholt wird und kein Teilproblem entsteht, das eigene Teilprobleme hat. Dann bringt der rekursive Aufruf keinen Erkenntnisgewinn.
• Beide Wege existieren oft: Für die Türme von Hanoi gibt es laut Düsseldorfer Programmierkurs auch einen iterativen Lösungsalgorithmus ohne Rekursion. Daraus folgt für den Unterricht, dass Schüler die beiden Lösungswege nebeneinander bewerten können, statt Rekursion als einzig richtigen Weg zu lernen.

Für die Bewertung eignen sich Kriterien, die die Klasse selbst formulieren kann: Wie leicht ist der Ablauf zu erklären? Wie gut spiegelt der Code die Problemstruktur? Wie nachvollziehbar ist der Ablauf beim Verfolgen von Hand? Ein pauschales „schneller“ oder „kürzer“ lässt sich aus den vorliegenden Quellen nicht belegen und sollte nicht als Merksatz erscheinen.

Einstiegsbeispiele in sinnvoller Reihenfolge

Der Aufbau vom Alltagsbild über die Fakultät zu den Türmen von Hanoi folgt einer steigenden Komplexität. Jedes Beispiel führt genau eine neue Idee ein.

Alltagsbild: Selbstähnlichkeit

Ineinandergestellte Matrjoschka-Puppen zeigen, dass in einem Objekt ein kleineres Objekt gleicher Art steckt. Öffnet man die Puppe, findet man die nächste, bis die kleinste Puppe nichts mehr enthält. Diese letzte Puppe steht für die Abbruchbedingung.

Fakultät als erste Methode

Bei der Fakultät lässt sich die Idee in einem Satz fassen: Die Fakultät einer Zahl ist die Zahl multipliziert mit der Fakultät ihres Vorgängers. Beim kleinsten zulässigen Wert endet die Berechnung. In Java ist das eine gewöhnliche Methode, die im Rumpf ihren eigenen Namen aufruft, zuvor aber prüft, ob der Abbruchfall vorliegt. Weil das Beispiel auch mit einer Schleife lösbar ist, eignet es sich gut für den ersten Vergleich beider Ansätze.

Türme von Hanoi als Zerlegungsbeispiel

Hanoi zeigt, dass ein Problem sich in kleinere Teilprobleme aufteilen lässt und dass dabei mehrere rekursive Aufrufe entstehen können. Der Einstieg gelingt über die Regeln, die der Programmierkurs der Universität Düsseldorf so festhält:

• Eine Scheibe pro Zug: Es darf immer nur genau eine Scheibe bewegt werden.
• Nur die oberste Scheibe: Bewegt werden darf nur die oberste Scheibe eines Stabs.
• Keine größere auf einer kleineren: Eine größere Scheibe darf nie auf eine kleinere gelegt werden.

Sinnvoll ist es, die Klasse das Spiel zunächst mit wenigen Scheiben selbst spielen zu lassen. Erst danach wird die Strategie formuliert: Das große Problem wird auf kleinere, einfacher lösbare Teilprobleme zurückgeführt. Diese Denkfigur kennen Schüler später bei Mergesort wieder.

Selbstähnliche Figuren als Anschluss

Wer Hanoi und Fakultät sicher beherrscht, kann zu selbstähnlichen Figuren übergehen. Ein Beispiel ist die Kochkurve; wie sich die kochkurve programmieren lässt, behandelt ein eigener Beitrag.

Wie eine rekursive Methode abläuft

Jeder rekursive Aufruf wartet auf das Ergebnis des nächsten, bis der Abbruchfall erreicht ist. Erst dann werden die offenen Aufrufe in umgekehrter Reihenfolge abgeschlossen. Wer diesen Ablauf versteht, kann auch unbekannte rekursive Methoden analysieren.

Der Begriff Terminierung beschreibt, dass die Folge der Aufrufe tatsächlich endet. Dafür braucht jede rekursive Methode eine Abbruchbedingung, die der Lehrplan ausdrücklich als Inhalt nennt. Zusätzlich muss jeder Aufruf dem Abbruchfall näherkommen, indem das Teilproblem kleiner wird. Fehlt eines von beidem, endet die Berechnung nicht.

Hilfreich ist ein Aufrufbaum oder Aufrufstapel auf Papier. Bei linearer Rekursion entsteht eine Kette, bei verzweigter Rekursion wie bei Hanoi verästelt sich der Baum. Die Zeichnung macht sichtbar, welcher Aufruf auf welchen wartet.

Typische Schülerfehler und wie man sie sichtbar macht

Die meisten Fehler entstehen an den drei Stellen, die das Prinzip ausmachen: Abbruch, Verkleinerung und Ergebnisweitergabe.

• Abbruchbedingung fehlt: Die Methode ruft sich auf, ohne jemals zu prüfen, ob schon alles erledigt ist. Die Aufrufkette endet dann nicht.
• Abbruchbedingung wird nie erreicht: Die Prüfung steht zwar da, aber das Teilproblem wird nicht kleiner. Hier fehlt die Terminierung, obwohl der Code auf den ersten Blick vollständig wirkt.
• Ergebnis wird verworfen: Der innere Aufruf wird ausgeführt, sein Rückgabewert aber nicht weiterverwendet. Das Zeichnen der wartenden Aufrufe deckt den Fehler schnell auf.
• Rekursion als Zauberei: Schüler vertrauen darauf, dass der Aufruf „irgendwie“ das Teilproblem löst. Dagegen hilft, einen Aufruf mit kleiner Eingabe vollständig von Hand zu verfolgen.
• Linear und verzweigt vermischt: Wer nur die Fakultät kennt, erwartet immer eine einzelne Kette. Hanoi korrigiert diese Vorstellung.

Als Prüfroutine für jede neue Methode bieten sich drei Fragen an: Wo endet die Rekursion? Wird das Teilproblem tatsächlich kleiner? Wird das Ergebnis des Aufrufs weiterverwendet? Damit lässt sich ein Großteil der Fehler ohne Ausführen des Programms finden.

Frequently asked questions

Können Schüler die Türme von Hanoi selbst in Java umsetzen?

Ja. Der Programmierkurs der Universität Düsseldorf schreibt dafür ein Java-Programm, das die Züge zum Lösen des Spiels ausgibt. Als Erweiterung nennt er die Aufgabe, die Anzahl der Scheiben als Argument beim Programmstart anzugeben.

Was unterscheidet lineare von verzweigter Rekursion?

Der Lehrplan nennt beide Formen als Inhalt. Bei der linearen Rekursion folgt auf jeden Aufruf höchstens ein weiterer, bei der verzweigten können mehrere Aufrufe entstehen. Die Fakultät steht für den ersten Fall, die Türme von Hanoi für den zweiten.

Welche Beispielaufgaben nennt der Lehrplan?

Der LehrplanPLUS G9 Informatik führt die Berechnung des ggT, die Erzeugung selbstähnlicher Figuren und die Türme von Hanoi auf. Die Fakultät als erstes Beispiel ergänzt diese Liste sinnvoll, weil sie auch iterativ lösbar ist.

Genügt ein einziges Beispiel, etwa nur Hanoi?

Nein. Hanoi zeigt Zerlegung und verzweigte Aufrufe, vermittelt aber nicht die einfachste Form mit einer Aufrufkette. Eine Reihe aus mehreren Beispielen ermöglicht den im Lehrplan geforderten Vergleich zwischen iterativer und rekursiver Lösung.