Rekursion

Java Insel: ​Rekursive Methoden

Viele Datenstrukturen der Informatik wie z. B. Arrays, Listen oder Bäume beruhen auf Selbstähnlichkeit. Ein probates Verfahren zum Umgang mit selbstähnlichen Datenstrukturen oder Problemen ist die Rekursion. Rekursion beruht darauf, dass ein Problem schrittweise gelöst wird, indem es bei jedem Schritt auf ein kleineres identisches Problem und eine (oder mehrere) einfache Operation(en) zurückgeführt wird. Zur Lösung des kleineren identischen Problems ruft eine rekursive Methode sich selbst mit einem veränderten Parameter (dem verkleinerten Problem) auf.

Beispiel: Berechnung der Fakultät

Die Fakultät kann mathematisch wie folgt definiert werden:

\[ n!=\left\{\begin{array}{ll} 1 & \mbox{für } n = 0\\ n (n-1)! & \mbox{sonst} \end{array}\right. \]

In der unteren Zeile wird die Berechnung von \(n!\) umgeformt in das Produkt \(n (n-1)!\). Der Faktor \((n-1)!\) ist dabei das um eins verkleinerte Problem Fakultät und die Multiplikation mit \(n\) ist die einfache Operation. Die Implementierung in Java lässt sich aus der mathematischen Formulierung direkt ableiten (zum Vergleich die iterative Variante rechts):

rekursiv	iterativ
/** * Berechnet rekursiv n! * @param n n * @return n! */ public static int fakultaet(int n) { if (n == 0) { return 1; } return n * fakultaet(n - 1); }	/** * Berechnet iterativ n! * @param n n * @return n! */ public static int fakultaet(int n) { int f = 1; for (int i = 1; i <= n; i++) { f = f * i; } return f; }

Der rekursive Aufruf erfolgt in der letzten Zeile return n * fakultaet(n - 1);. Vor dem Aufruf wird der aktuelle Wert von n auf dem Stack gesichert und wiederhergestellt, sobald der Aufruf zurückkehrt. So lange der aktuelle Wert von n größer als Null ist, kommt es nie zur Berechnung des Ergebnisses, da vor der Multiplikation stets der rekursive Aufruf erfolgt. Alle Faktoren werden also beim jeweiligen Aufruf auf dem Stack gesichert und die Multiplikationen erst ausgeführt, wenn die Aufrufe zurückkehren. Die eigentliche Berechnung des Produkts erfolgt gewissermaßen auf dem Rückweg.

Im Vergleich der beiden Methoden fällt auf, dass die rekursive Variante weniger komplex notiert werden kann. Der Laufzeitbedarf der beiden Methoden ist identisch: Die Schleife der iterativen Variante wird n mal durchlaufen und bei der rekursiven Variante erfolgen n Methodenaufrufe.

Demgegenüber ist der Speicherbedarf der rekursiven Variante höher: die iterative Methode hat konstanten Speicherbedarf von zwei int Variablen, während die rekursive Variante für jeden Aufruf eine int Variable (n) auf dem Stack ablegt.

Abbruchbedingung und Rekursionsschritt

Den Ausdruck if (n == 0) {...} im obigen Beispiel nennt man die Abbruchbedingung und den erneuten Aufruf fakultaet(n - 1) den Rekursionsschritt der Rekursion. Jede Rekursion muss unbedingt mit einer Abbruchbedingung versehen sein und diese muss vor der Ausführung des Rekursionsschritts geprüft werden.

Fehlt die Abbruchbedingung, kommt es zu einer Endlosrekursion:

public static void endlos() {
    endlos();
}

Eine Endlosrekursion unterscheidet sich von einer Endlosschleife darin, dass sie nicht wirklich endlos laufen kann, da mit jedem rekursiven Aufruf der aktuelle Zustand der Methode auf dem Stack gesichert wird. Normalerweise werden diese Daten bei der Rückkehr des Aufrufs wieder vom Stack genommen. Da es bei einer Endlosrekursion nicht zur Rückkehr zur aufrufenden Methode kommt, wächst der Stack immer weiter an und das Programm stürzt letztlich wegen Speichermangels mit einem ​StackOverflowError ab.

Die Abbruchbedingung sorgt dafür, dass die Methode beendet wird, sobald das zu lösende Problem irreduzibel ist.

Beispiel: Berechnung von 2ⁿ

/*
 * Berechnet rekursiv 2^n
 * @param n n
 * @return 2^n
 */
public static int zweihoch(int n) {
    if (n == 0) {
        return 1;
    }
    return 2 * zweihoch(n - 1);
}

Beispiel: Berechnung des größten gemeinsamen Teilers

/*
 * Berechnet rekursiv den ggT mit dem Turbo-Euklid
 * @param x erste Zahl
 * @param y zweite Zahl
 * @return ggT von x und y
 */
public static int ggT(int x, int y) {
    if (y == 0) {
        return x;
    }
    return ggT(y, x % y);
}

Hierbei handelt es sich um eine endrekursive Implementierung.

Beispiel: Fibonacci Zahlen

/**
 * Berechnet rekursiv die n-te Fibonacci Zahl
 * @param n n
 * @return
 */
public static int fibonacci(int n) {
    if (n <= 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Die Türme von Hanoi

/*
 * Gibt die Anweisungen fuer die Zuege des Spiels Tuerme von Hanoi aus.
 * @param n Anzahl der Scheiben
 * @param start Name des Startplatzes
 * @param lager Name des Zwischenlagers
 * @param ziel Name des Zielplatzes
 */
public static void tuermeVonHanoi(int n, String start, String lager, String ziel) {
    // Abbruchbedingung: Wenn keine Scheibe verlegt werden soll -> mach nichts
    if (n > 0) {
        tuermeVonHanoi(n - 1, start, ziel, lager);

        System.out.println("Lege Scheibe " + n + " von " + start + " nach " + ziel);

        tuermeVonHanoi(n - 1, lager, start, ziel);
    }
}

Java Insel

​Die Türme von Hanoi

Beispiel: Palindrom analysieren

/**
 * Bestimmt rekursiv, ob der übergebene String ein Palindrom ist. Ignoriert
 * Groß-/Kleinschreibung. Liefert für Strings der Länge 0 oder 1 true zurück.
 * 
 * @param s
 * @return
 */
public static boolean istPalindrom(String s) {
    if (s.length() <= 1) {
        return true;
    }

    // Großbuchstaben eliminieren
    s = s.toLowerCase();
    // Sind erstes und letztes Zeichen gleich?
    if (s.charAt(0) != s.charAt(s.length() - 1)) {
        // nein -> kein Palindrom
        return false;
    }
        
    return istPalindrom(s.substring(1, s.length() - 1));
}

Rekursion auf Arrays

Bei der Rekursion auf Arrays wird ein Array als Parameter der rekursiven Methode verwendet. Die Verkleinerung des Problems erfolgt dadurch, dass in der Methode eine Operation mit der ersten (oder ggf. letzten) Zelle des Arrays durchgeführt wird und die Methode mit dem Rest des Arrays (das Array ohne die bereits bearbeitete Zelle) rekursiv aufgerufen wird. Rekursionsende ist, wenn alle Zellen des Arrays bearbeitet wurden.

Dieser Mechanismus lässt sich auf zwei verschiedene Arten implementieren: Entweder liefert man stets den Index der aktuellen Zelle als zusätzlichen Parameter mit, oder man liefert stets eine um die aktuelle Zelle verkleinerte Kopie des Arrays mit.

Der Nachteil der ersten Variante ist, dass man eine Wrapper-Methode benötigt, um den zusätzlichen Parameter zu verstecken, der Nachteil der zweiten Variante ist, dass stets eine Kopie des Arrays erzeugt werden muss, was eine teure Operation ist.

// mit Wrapper, Übergabe eines zusätzlichen Parameters
    public static int summeRekursiv(int[] a, int pos) {
        if (pos == a.length - 1) {
            return a[pos];
        }
        return a[pos] + summeRekursiv(a, pos + 1);
    }
    
// Wrappermethode für summeRekursiv
    public static int summe(int[] a) {
        return summeRekursiv(a, 0);
    }
    
// ohne Wrapper, mit Kopie des Arrays
    public static int summe2(int[] a) {
        if (a.length == 0) {
            return 0;
        }
        return a[0] + summe2(Arrays.copyOfRange(a, 1, a.length));
    }