Q1.3 – Rekursion als Modellierungsstrategie

Q1.2 wird hier nicht wiederholt. Die bekannten Verfahren dienen als Referenzpunkte: lineare Suche prüft nacheinander, binäre Suche halbiert einen sortierten Suchraum, Insertion Sort baut einen sortierten Bereich auf, Quicksort trennt Daten um ein Pivot. Q1.3 fragt nun: Welche dieser Ideen lassen sich als Folge kleinerer Teilprobleme derselben Art beschreiben?

Damit ändert sich die Leitfrage. Q1.2 untersuchte Such- und Sortierstrategien und deren Laufzeit. Q1.3 untersucht, ob ein Verfahren besser als Schleifensteuerung oder als rekursive Teilproblemstruktur modelliert werden kann.

Der Einstieg in Rekursion ist nicht der Satz „Eine Methode ruft sich selbst auf“. Das ist nur die spätere Implementationsform. Fachlich beginnt Rekursion mit einer Strukturidee: Eine Aufgabe wird auf eine kleinere Aufgabe derselben Art zurückgeführt.

In einer Implementierung wird die Problemstruktur zur Methode. Die Methode prüft zuerst den Basisfall. Wenn dieser nicht erreicht ist, ruft sie sich mit veränderten Parametern erneut auf. Die Parameter tragen den Zustand des aktuellen Teilproblems.

int summeBis(int n) {
    if (n <= 0) return 0;       // Basisfall / Terminierung
    return n + summeBis(n - 1); // Rekursionsschritt
}

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Eine Visualisierung rekursiver Abläufe muss mehr zeigen als eine dekorative Baumform. Sie soll verständlich machen, welche Aufrufe gerade offen sind, wann der Basisfall erreicht wird und in welcher Reihenfolge Rückgabewerte wieder nach oben wandern.

Rekursion ist nicht auf Such- und Sortierverfahren beschränkt. Sie wird besonders anschaulich, wenn eine Struktur kleinere Versionen ihrer selbst enthält: ein Ast verzweigt in kleinere Äste, eine Figur enthält kleinere Kopien, eine mathematische Funktion verweist auf einen kleineren Eingabewert.

void zeichneAst(double laenge) {
    if (laenge < 10) return;          // Basisfall

    zeichneLinie(laenge);
    drehe(-30);
    zeichneAst(laenge * 0.65);        // linker Teilast
    drehe(60);
    zeichneAst(laenge * 0.65);        // rechter Teilast
    drehe(-30);
}

long fakultaet(int n) {
    if (n <= 1) return 1;
    return n * fakultaet(n - 1);
}

Der Unterschied liegt in der Form der Teilprobleme. Fakultät und Summe verkleinern linear. Die rekursive Grafik erzeugt mehrere Teilfiguren und ist damit ein anschauliches Beispiel für mehrfache Rekursion.

Iteration steuert Wiederholung explizit über Schleifen und Zustandsvariablen. Rekursion steuert Wiederholung über neue Aufrufe mit veränderten Parametern. Beide können denselben Algorithmus beschreiben. Rekursion ist nicht automatisch effizienter, und Iteration ist nicht automatisch verständlicher.

Fokussierter Vergleich: binäre Suche

int binaereSucheIterativ(int[] a, int suchwert) {
    int links = 0;
    int rechts = a.length - 1;

    while (links <= rechts) {
        int mitte = (links + rechts) / 2;
        if (a[mitte] == suchwert) return mitte;
        if (a[mitte] < suchwert) links = mitte + 1;
        else rechts = mitte - 1;
    }
    return -1;
}

int binaereSucheRekursiv(int[] a, int suchwert, int links, int rechts) {
    if (links > rechts) return -1;

    int mitte = (links + rechts) / 2;
    if (a[mitte] == suchwert) return mitte;
    if (a[mitte] < suchwert) {
        return binaereSucheRekursiv(a, suchwert, mitte + 1, rechts);
    }
    return binaereSucheRekursiv(a, suchwert, links, mitte - 1);
}

Backtracking ist ein rekursionsnahes Suchverfahren für Entscheidungsräume. Eine Lösung wird schrittweise aufgebaut. Führt eine Entscheidung in eine Sackgasse, wird sie zurückgenommen und eine andere Möglichkeit ausprobiert.

boolean sucheLoesung(Zustand z) {
    if (istLoesung(z)) return true;

    for (Entscheidung e : moeglicheEntscheidungen(z)) {
        wendeAn(z, e);
        if (sucheLoesung(z)) return true;
        macheRueckgaengig(z, e);
    }
    return false;
}

Backtracking passt deshalb gut zum erhöhten Niveau: Es verbindet Rekursion, Entscheidung, Zustandsänderung und Rücknahme zu einem Suchverfahren, ohne dass die Seite in ein vollständiges Sudoku- oder n-Damen-Kapitel ausufern muss.

Das Werkzeug Such- und Sortieralgorithmen visualisieren ist für Q1.3 ein Vergleichsinstrument. Es bietet lineare und binäre Suche sowie Insertion Sort und Quicksort in iterativen und rekursiven Varianten. Sichtbar werden unter anderem Schritttexte, Markierungen, Vergleichszahlen, Tausch- bzw. Verschiebeoperationen, der Suchschlüssel und eine Vergleichskurve über mehrere Läufe.

Damit bleibt die Toolaussage präzise: Es visualisiert Abläufe, Markierungen und Kennzahlen rekursiver und iterativer Varianten. Die Aufrufstruktur und der Speicherbedarf müssen aus Schritttext, Parametern und dem in dieser Seite entwickelten Stackmodell fachlich rekonstruiert werden.

Am Ende von Q1.3 steht keine Regel „Rekursion ist besser“ oder „Iteration ist besser“. Die fachliche Leistung besteht darin, die Modellierungsentscheidung zu begründen.

So schließt Q1.3 an Q1.2 an: Such- und Sortieralgorithmen bleiben vertraute Referenzpunkte, aber die Begründung wird tiefer. Es geht nicht nur um „funktioniert“ und „wie schnell“, sondern um die Frage, welche Struktur ein Problem hat und welche algorithmische Darstellung diese Struktur am besten sichtbar macht.