Bayern Abitur Informatik

Was Rekursion ist

Ein Algorithmus oder eine Methode heißt rekursiv, wenn sie sich zur Lösung einer Aufgabe selbst wieder aufruft, und zwar mit einer kleineren oder einfacheren Version derselben Aufgabe. Die Grundidee besteht darin, ein Problem auf ein gleichartiges, aber kleineres Problem zurückzuführen, bis die Lösung so einfach ist, dass sie ohne weiteren Aufruf angegeben werden kann.

Jede korrekte rekursive Methode hat zwei Bestandteile.

• Die Abbruchbedingung (auch Rekursionsanker oder Basisfall) behandelt den einfachsten Fall direkt und ruft die Methode nicht mehr auf.
• Der rekursive Aufruf löst den übrigen Fall, indem er dieselbe Methode mit einem Argument aufruft, das näher an der Abbruchbedingung liegt.

Fehlt die Abbruchbedingung, oder nähert sich das Argument ihr nie an, dann endet die Rekursion nicht. Bei Java führt das nach einiger Zeit zu einem StackOverflowError, weil jeder Aufruf Speicherplatz auf dem Aufrufkeller (Stack) belegt und dieser irgendwann voll ist.

Lineare Rekursion

Bei der linearen Rekursion führt jeder Aufruf höchstens einen weiteren rekursiven Aufruf aus. Die Aufrufe bilden eine Kette. Das Standardbeispiel ist die Fakultät, $n! = n \cdot (n-1)!$ mit $0! = 1$.

public static int fakultaet(int n) {
    if (n == 0) {
        return 1;                       // Abbruchbedingung
    }
    return n * fakultaet(n - 1);        // rekursiver Aufruf
}

Für fakultaet(3) entsteht zuerst die Aufrufkette, dann wird von innen nach außen zurückgerechnet:

Die Multiplikationen werden erst ausgeführt, wenn der innerste Aufruf 1 zurückgegeben hat. Bis dahin warten alle äußeren Aufrufe mit ihren Zwischenwerten auf dem Stack.

Der größte gemeinsame Teiler

Der euklidische Algorithmus ist von Natur aus rekursiv. Der ggT zweier natürlicher Zahlen ändert sich nicht, wenn man die größere durch den Rest der Division ersetzt, und der ggT von $a$ und $0$ ist $a$.

public static int ggT(int a, int b) {
    if (b == 0) {
        return a;
    }
    return ggT(b, a % b);
}

Für ggT(84, 36) ergibt sich $\text{ggT}(84,36) \to \text{ggT}(36,12) \to \text{ggT}(12,0) = 12$. Auch das ist lineare Rekursion, denn jeder Aufruf erzeugt genau einen weiteren. Die zweite Zahl wird in jedem Schritt echt kleiner (der Rest ist kleiner als der Teiler), deshalb wird die Abbruchbedingung sicher erreicht.

Verzweigte Rekursion

Bei der verzweigten Rekursion (auch baumartige Rekursion) ruft sich die Methode pro Aufruf mehrfach selbst auf. Die Aufrufe bilden dann einen Baum statt einer Kette. Das bekannteste Beispiel sind die Fibonacci-Zahlen mit $F_0 = 0$, $F_1 = 1$ und $F_n = F_{n-1} + F_{n-2}$.

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Die Zahl der Aufrufe $A(n)$ erfüllt $A(0) = A(1) = 1$ und $A(n) = 1 + A(n-1) + A(n-2)$. Daraus folgt $A(2)=3$, $A(3)=5$, $A(4)=9$, $A(5)=15$, $A(6)=25$. Für fib(5) werden also 15 Aufrufe ausgeführt, obwohl nur sechs verschiedene Werte vorkommen, denn fib(3) wird zum Beispiel zweimal berechnet. Die Aufrufzahl wächst etwa um den Faktor 1,6 pro Erhöhung von $n$ um 1, also exponentiell. Das ist ein Grund, warum verzweigte Rekursion bei mehrfach auftretenden Teilproblemen teuer werden kann.

Türme von Hanoi

Drei Stäbe A, B und C, auf A liegen $n$ Scheiben der Größe nach gestapelt, die größte unten. Alle Scheiben sollen nach C, wobei jeweils nur eine Scheibe bewegt wird und nie eine größere auf einer kleineren liegen darf. Die rekursive Lösung folgt aus einer einfachen Überlegung.

1. Bewege die oberen $n-1$ Scheiben von A nach B, und nutze dabei C als Hilfsstab.
2. Bewege die größte Scheibe von A nach C.
3. Bewege die $n-1$ Scheiben von B nach C, und nutze dabei A als Hilfsstab.

public static void hanoi(int n, char von, char nach, char hilf) {
    if (n == 0) {
        return;                                   // nichts zu bewegen
    }
    hanoi(n - 1, von, hilf, nach);
    System.out.println("Scheibe " + n + ": " + von + " nach " + nach);
    hanoi(n - 1, hilf, nach, von);
}

Die Zahl der Züge erfüllt $Z(n) = 2 \cdot Z(n-1) + 1$ mit $Z(0) = 0$, also $Z(n) = 2^n - 1$. Für $n = 3$ sind das 7 Züge, für $n = 10$ schon 1023. Die Verdopplung pro Scheibe zeigt, dass die Aufgabe für große $n$ nicht mehr praktisch lösbar ist, auch wenn der Algorithmus kurz und klar ist.

Selbstähnliche Figuren

Eine Figur ist selbstähnlich, wenn ein Teil von ihr eine verkleinerte Kopie des Ganzen ist. Solche Figuren lassen sich rekursiv zeichnen, wobei die Rekursionstiefe oder die Mindestgröße die Abbruchbedingung liefert. Als Beispiel ein Baum aus Linien in Pseudocode mit einer Zeichenschildkröte, die sich vorwärts bewegt und dreht:

Methode baum(laenge)
    wenn laenge < 4
        stopp
    vor(laenge)
    links(30)
    baum(laenge * 0,7)
    rechts(60)
    baum(laenge * 0,7)
    links(30)
    zurück(laenge)
endeMethode

Jeder Aufruf zeichnet einen Stamm und zwei kürzere Äste, die wieder genauso aufgebaut sind. Der Aufruf ist verzweigt, denn es gibt zwei rekursive Aufrufe, und die Schildkröte kehrt am Ende an ihre Ausgangsposition zurück, damit der nächste Zweig am richtigen Ort beginnt.

Rekursiv oder iterativ

Jede rekursive Methode lässt sich mit einer Schleife (iterativ) ausdrücken, und umgekehrt lässt sich jede Schleife rekursiv schreiben. Die Fakultät iterativ:

public static int fakultaetIterativ(int n) {
    int ergebnis = 1;
    for (int i = 2; i <= n; i++) {
        ergebnis = ergebnis * i;
    }
    return ergebnis;
}

Der Vergleich fällt je nach Problem unterschiedlich aus.

• Die rekursive Fassung ist oft kürzer und folgt der mathematischen Definition unmittelbar. Bei Strukturen, die selbst rekursiv aufgebaut sind (Listen, Bäume, Graphen), ist sie meist die natürliche Wahl.
• Die iterative Fassung braucht keinen Aufrufkeller und ist bei linearer Rekursion oft schneller und speichersparender. Sie vermeidet das Risiko eines Stack-Überlaufs bei sehr großer Tiefe.
• Bei verzweigter Rekursion mit überlappenden Teilproblemen (Fibonacci) ist die naive rekursive Lösung wesentlich langsamer als eine Schleife, die jeden Wert nur einmal berechnet.
• Bei Problemen wie den Türmen von Hanoi ist die iterative Lösung dagegen deutlich umständlicher als die rekursive.

Beim Nachvollziehen eines rekursiven Aufrufs hilft eine Tabelle, die jeden Aufruf mit seinen Argumenten und seinem Rückgabewert in der Reihenfolge festhält, in der sie begonnen und beendet werden.