Rekursion

Rekursion beschreibt, wenn ein Prozess sich selber aufruft. Dies wird oft bei Komposition verwendet (z.B. in Bäumen) oder auch um bestimmte mathematische Funktionen zu modellieren.

Rekursive Grafiken

Es gibt viele rekursive Bilder. Besonders bekannt ist die Mandelbrot-Menge:

Bild von By Wolfgang Beyer, Wikipedia.

Mathematische Funktionen

Ein beliebtes Beispiel hier ist die Fakultät, bei welcher eine Fakultät von $n$ auch als $n$ mal die Fakultät von $n-1$ beschrieben werden kann.

Teile und Herrsche Prinzip

Das “Teile und Herrsche”-Prinzip (eng.: Divide and Conquer principle) ist ein algorithmischer Lösungsansatz, welcher besagt, dass komplexe Probleme rekursiv aufgeteilt werden können, bis die Lösung für einen solchen kleinen Teil trivial ist.

Bekannte Beispiele für Algorithmen, welche dieses Prinzip verwenden, sind z.B.: Binary Sort und Quick Sort.

Beispiel: Fakultät in Java

void main() {
  final int start = 5;
  final int factorial = factorial(start);
  IO.println("Die Fakultät %d! ergibt %d".formatted(
    start, factorial
  ));
}

int factorial(int n) {
  if (n == 1) {
    return 1;
  }
  // Rekursion: factorial(int) ruft sich selber auf
  return n * factorial(n - 1);
}

Vergleich mit Iteration

Vorteile von Rekursion

• Rekursive Lösungsansätze können oft kürzer und einfacher sein.
• Rekursion mit “Teile und Herrsche”-Prinzip: Multithreading kann möglich sein.

Nachteile von Rekursion

• Extra overhead bei Methodenaufruf.
• Schwer debuggable (nicht lesbare Stacktraces).
• Fehleranfällig bei falsch deklarierten Abbruchbedingungen.

// Fakultät ohne Rekursion
int factorial(int n) {
  int out = 1;
  for (int i = 2; i <= n; i++) {
    out *= i;
  }
  return out;
}