UniProMax/Programmiergrundlagen/rekursion

Rekursion

Funktionen, die sich selbst aufrufen. Mit Call-Stack-Visualisierung am Beispiel Fakultät.

2LerneinheitenVoraussetzungen:Funktionen

Relevant für:Informatik(Klausurniveau)Wirtschaftsinformatik(Grundlagen)

Sprache wählen

Sprache

Lerneinheit 1 von 2java

Rekursion

Rekursion ist eine Technik, bei der eine Funktion sich selbst aufruft. Klingt seltsam, ist aber für viele Probleme die natürlichste Lösung.

Klassisches Beispiel: Fakultät

Die Fakultät einer Zahl n ist n × (n-1) × (n-2) × ... × 1. Mathematisch:

n! = n × (n-1)!

Genau das schreiben wir auch im Code:

java// snippet

public static int fakultaet(int n) {
  if (n <= 1) {
    return 1;             // Basisfall
  }
  return n * fakultaet(n - 1);  // Rekursiver Aufruf
}

Zwei Bestandteile, immer

Jede rekursive Funktion braucht:

Basisfall: wann hört die Rekursion auf? Hier: n <= 1 gibt 1 zurück.
Rekursiver Schritt: ruft sich selbst mit kleinerem Problem auf.

Wenn der Basisfall fehlt, ruft die Funktion sich endlos selbst auf. Stack overflow.

Was passiert intern

fakultaet(4) führt zu vier verschachtelten Aufrufen, die nacheinander zurückgeben:

java// snippet

fakultaet(4)
= 4 * fakultaet(3)
= 4 * 3 * fakultaet(2)
= 4 * 3 * 2 * fakultaet(1)
= 4 * 3 * 2 * 1
= 24

Jeder Aufruf landet auf dem Call Stack und wartet, bis die tieferen Aufrufe fertig sind. Erst dann wird zurückgerechnet. Im interaktiven Abschnitt kannst du das Schritt für Schritt selbst sehen.

Wann Rekursion?

Bäume durchgehen (Dateisystem, JSON, HTML-DOM)
Mathematische Definitionen, die sich auf sich selbst beziehen
Divide-and-Conquer-Algorithmen (Mergesort, Quicksort)

Wann nicht: einfache Schleifen sind oft schneller und klarer.

VorkenntnisFunktionen Mehr Themen entdeckenZurück zur Startseite