# Rekursion

* Selbstaehnlichkeit -> *Ein Verzeichnis enthaelt Dateien und andere Verzeichnisse*

## Iteration vs. Rekursion

**Iteration**

> Wiederholend

```java

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**

```java

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)

```java
FUCK
```

## Permute
Durchprobieren aller Moeglichkeiten