Q1.3 – Rekursion als Modellierungsstrategie

Als Referenz dienen bekannte Suchalgorithmen und Sortieralgorithmen: lineare Suche (sequentielles Durchlaufen) und Sortieren durch Einfügen (sukzessive Einordnung). Beide arbeiten primär mit Schleife, Index/Zähler und lokalem Zustandsupdate.

int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == key) return i;
    }
    return -1;
}

void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int x = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > x) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
}

Vergleich A: Binäre Suche

int binarySearchIter(int[] a, int key) {
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (a[m] == key) return m;
        if (key < a[m]) r = m - 1;
        else l = m + 1;
    }
    return -1;
}

int binarySearchRec(int[] a, int key, int l, int r) {
    if (l > r) return -1;
    int m = (l + r) / 2;
    if (a[m] == key) return m;
    if (key < a[m]) return binarySearchRec(a, key, l, m - 1);
    return binarySearchRec(a, key, m + 1, r);
}

Konkreter Vergleich (binäre Suche): Beide Varianten halbieren denselben Suchraum. Iterativ ändern sich nur l/r in einer Schleife, rekursiv entstehen nacheinander Aufrufe wie (l,r)=(0,15)→(8,15)→(12,15).

Vergleich B: Sortierstrategie

void quicksort(int[] a, int l, int r) {
    if (l >= r) return;                     // Basisfall
    int p = partition(a, l, r);             // Zerlegung um Pivot
    quicksort(a, l, p - 1);                 // Teilproblem links
    quicksort(a, p + 1, r);                 // Teilproblem rechts
}

Der Effizienzgedanke wurde in Q1.2 eingeführt und wird hier präzisiert: Nicht nur „funktioniert?“, sondern wie gut skaliert die Modellierungsentscheidung? Relevante Indikatoren sind Anzahl von Vergleichen, notwendige Schritte und zusätzlicher Speicher (z. B. Aufrufstack).

Rekursion ist damit nicht nur Syntax, sondern ein tragfähiges Modell für strukturierte Problemlösung in der Algorithmik.

Präzisierung: Bei der binären Suche geschieht Teile-und-herrsche als wiederholte Halbierung des Intervalls; bei Quicksort als Zerlegung um ein Pivot in zwei Teilfolgen. Wichtig: Nicht jede Rekursion ist automatisch Divide-and-Conquer (z. B. Fakultät verkleinert nur linear).

Das Werkzeug Such- und Sortieralgorithmen visualisieren wird in Q1.3 als Vergleichsinstrument genutzt. Im Unterschied zu Q1.2 geht es hier nicht nur um Ablaufverständnis, sondern um die begründete Gegenüberstellung von Modellierungsentscheidungen.

• Vergleiche iterative und rekursive Binärsuche bei identischer Datenbasis.
• Nutze Insertion Sort (iterativ) und Quicksort (rekursiv), um Teile-und-herrsche zu reflektieren.
• Dokumentiere Kurvenverläufe der Vergleichszahlen und beziehe Speicheraspekte (Aufrufstack) ein.

Beobachtungsschwerpunkt: gleiche Eingabegröße wählen, dann Verlauf der Vergleichsanzahl über mehrere Läufe kontrastieren und begründen, warum sich die Kurven bei Halbierung, linearer Prüfung oder rekursiver Teilproblemstruktur unterschiedlich entwickeln.

Rückbezug: Die in Q1.2 eingeführten Metriken werden hier als Argumentationsgrundlage für Modellnähe, Lesbarkeit und Effizienzfolgen verwendet.

• Iteration ist oft naheliegend, wenn ein Ablauf linear und zustandsnah über Schleifen steuerbar ist.
• Rekursion ist besonders anschlussfähig, wenn die Problemstruktur selbst hierarchisch oder teilproblemorientiert ist.
• Rekursiv ist nicht automatisch besser: Lesbarkeit kann steigen, aber Stackkosten und ungünstige Fälle bleiben zu prüfen.
• Effizienz ist ein fachliches Kernkriterium, weil informatische Lösungen unter realen Datenmengen tragfähig sein müssen.

Anschluss: Diese Vergleichsperspektive baut auf den Grundlagen aus Q1.2 auf und bereitet direkt auf vertiefte Laufzeit- und Komplexitätsbetrachtungen der Qualifikationsphase vor.