AD.md

Rekursion

• Selbstaehnlichkeit -> Ein Verzeichnis enthaelt Dateien und andere Verzeichnisse

Iteration vs. Rekursion

Iteration

Wiederholend

public static int factorialIter(final int n) {
    int result = 1;
    for(int i =1; i <= n; i++) {
            result = result * i;
    }

    return result;
}

Rekursion

Schwieriges Problem wird auf ein gleichartiges, aber etwas einfacheres Problem zurueckgefuehrt

=> Rekursionsvorschrift

Wir brauchen immer eine Anfangsbedingung/Basis => Rekursionsbasis

public static int factorialRec(final int n) {
    if((n == 0) || (n == 1)) {  // Rekursionsbasis
        return 1;  // Rekursionsbasis
    }
    else {  // Rekursionsvorschrift
        return (n * factorialRec(n - 1)); // Rekursionsvorschrift
    }
}

Note: Die Bedingung fuer die Basis und Vorschrift gehoert explizit zur Begruendung!

Die Method ruft sich immer wieder selber auf, um auf das Endergebnis zu gelangen.

Auch wiederholend aber implizit rekursiv.

Call Stack

• Heap: Speicherbereich in dem Objekte gespeicher werden. Nicht mehr referenzierbare Objekte werden durch den GC geloescht
• Call Stack: Speicherbereich fuer aktuelle Methodenparameter und lokale Variablen. Pro Methodenaufruf wird ein Stack Frame angelegt und wieder geloescht nach Methodenabarbeitung.

Maechtigkeit der Rekursion

Rekursion und Iteration sind gleich maechtig! Probleme koennen mit beiden Methoden geloest werden.

Motivation fuer die Rekursion

• maechtiges Loesungskonzept
• haeufig einfache und elegante Problemloesungen
• weniger Quellcode
• Korrektheit haeufig einfacher zu zeigen
• Gewisse Programmiersprachen, wie List oder Prolog kennen nur Rekursionen

Tuecken der Rekursion

• schnell sehr viele Methodenaufrufe
• tendenziell langsamere Programmausfuehrung
• grosser Speicherbedarf auf dem call Stack
• Gefahr eines Stack Overflows!

Rekursions Typen

Lineare Rekursion

Die Ausfuehrung der Methode m(...) fuehrt zu hoechstens einem rekursiven Aufruf (Fakultaet)

Nichtlineare Rekursion

Die Ausfuehrung der Methode m(...) fuehrt zu mehr als einem rekursiven Aufruf.

• Nicht geschachtelt (primitiv rekursiv) -> m(...) -> m(...), m(...)
• Geschachtelt (nicht primitiv rekursiv) -> m(...) -> m(m(...)...) (Ackermann-Funktion)

Direkte Rekursion

Eine rek. Methode ruft sich direkt selbst auf

Indirekte Rekursion

Eine rek. Methode ruft sich indirekt selber auf. (ueber eine andere Methode)

FUCK

Permute

Durchprobieren aller Moeglichkeiten