Acht Stunden sieht der Lehrplan für Rekursion vor, acht Stunden, das ist absurd wenig für das, was sich das Schulbuch zumindest anbietet – Fakultät, Palindrom, Fibonacci, Ackermann, größter gemeinsamer Teiler, Hanoi, selbstähnliche Kurven (Sierpinksi, Hilbert, Pythagorasbaum, Drachenkurve); Rucksack- und 8-Damen-Problem; Tiefensuche, Tiefensuche-Varianten und Vergleich mit Dijkstra, Breitensuche. Natürlich muss man nicht alles davon machen, aber viel davon auch implementieren. Und Backtracking ist nichts, was leicht fällt.

Der Lehrplan, mit seiner unsinnigen Trennung von Kompetenzerwartungen und Inhalten, sieht für diese 8 Stunden zu je 45 Minuten vor:

Kompetenzerwartungen

Die Schülerinnen und Schüler …

• analysieren rekursive Algorithmen und erläutern das Prinzip der Rekursion. Dabei vergleichen sie iterative und rekursive Algorithmen für geeignete Problemstellungen.
• implementieren rekursive Algorithmen zur Lösung von Problemen und Aufgaben, wie z. B. Berechnung des ggT, Erzeugung selbstähnlicher Figuren, Türme von Hanoi.
• erläutern die Idee der Tiefensuche in Graphen, formulieren den zugehörigen Algorithmus und wenden diesen an konkreten Beispielen an.
• implementieren die Tiefensuche in Graphen und modifizieren den Algorithmus in geeigneter, vom Anwendungskontext abhängiger Weise, z. B. bei der Auswahl oder Bearbeitung aller erreichbaren Knoten mit bestimmten Eigenschaften.

Inhalte zu den Kompetenzen:

• Rekursion: rekursiver Aufruf, Abbruchbedingung, lineare und verzweigte Rekursion
• Tiefensuche

Nun ja. Ich habe für meinen Kurs versucht, das 8-Damen-Problem zu veranschaulichen:

In Java wäre das:

void loesungsmethode(int spalte) {  
    for (int zeile=0; zeile<8; zeile++) {
        if ( feldIstMoeglich(zeile, spalte) ) {
            setzeDame(zeile, spalte);
            if (spalte==7) druckeSchachbrettAus();
            else loesungsmethode(spalte+1);                    
            entferneDame(zeile, spalte);
        }
    }
}

Gestartet wird das mit dem Aufrufen von loesungsmethode(0) für die erste Spalte. Wenn das Ergebnis gefunden ist, muss man es ausgeben, weil bei diesem Vorgehen ja nach und nach alle je gesetzten Damen wieder entfernt werden. (Man kann es auch schwieriger machen, siehe Schulbuch. Die Methoden setzeDame und entferneDame erleichtern den Zugriff auf das Schachbrett, das dort als ArrayList<ArrayList<Boolean>> modelliert ist. Meine Güte.)

void setzeDame(int zeile, int spalte) {
    schachbrett.get(zeile).set(spalte, true);
 }
void entferneDame(int zeile, int spalte) {
    schachbrett.get(zeile).set(spalte, false);
}

Nachtrag:

Auch sonst bin ich mit dem an sich sehr guten Buch in manchen Punkten doch nicht zufrieden. Der Pseudocode für die rekursive Methode der Tiefensuche lautet:

methode KnotenBesuchen(aktuell:GANZZAHL)
besuchteKnoten.Hinzufügem(aktuell)
...

Zur bayerischen Unsitte, die Methodenbezeichner mit Großbuchstaben anfangen zu lassen und im Infinitiv zu verfassen (selber bin ich Team „besucheKnoten“), sage ich mal nichts. Dass mit GANZZAHL versucht wird, das ganze abstrakt und sprachunabhängig zu halten, verstehe ich. Aber mit der Zeile „besuchteKnoten.Hinzufügen(aktuell)“ lege ich mich doch schon wieder darauf fest, eine ArrayList<Integer> für die markierten Knoten zu verwenden, und dann auch eine ArrayList<ArrayList<Integer>> für die Adjazenzmatrix zu verwenden, und nicht jeweils Arrays, was für die Schüler und Schülerinnen sehr viel anschaulicher wäre. Warum nicht allgemeiner:

methode KnotenBesuchen(aktuell:GANZZAHL)
markiereAlsBesucht(aktuell)
...

und der Implementierung überlassen, wie man den Knoten als besucht markieren will? Die Möglichkeit, ein Attribut „besucht“ für jeden Knoten anzulegen, wird immerhin in einer Aufgabe vorgeschlagen.