Rekursion

Java Insel: ​Rekursive Methoden

Methoden rufen sich selbst auf...

Spiegel

Beispiel: Berechnung der Fakultät

\[ n! = \left{ x ^ 2 \in \mathcal{O}(n\, log\, n) \]

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; }

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.

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);
}

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, char start, char lager, char 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