Rekursion

Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst:

• rekursive Methoden

• rekursive Datenstrukturen

rekursive Methoden

Rekursive Methoden sind Methoden, die sich selber aufrufen, um z.B. eine Berechnug auszuführen.

Wichtig sind dabei folgende Elemente:

• ein Parameter, in dem man je nach Rekursionsstufe einen anderen Wert übergeben kann.

• eine Abbruchbedingung für das Rekursionsende - sonst läuft die Methode ewig weiter.

• ein (oder mehrere) rekursive Aufrufe.

einfaches Beispiel

Die folgende rekursive Methode berechnet n! = 1*2*3*...*n

// rekursive Methode mit Parameter

// n wird bei jedem Aufruf eins runtergezählt!
public int fakultaet(int n) {
  //Abbruchbedingung
  if (n <= 1) {
    return 1;
  }
  // rekursiver Aufruf fuer n-1
  int zahl = fakualtaet(n-1);

  // Sachlogik
  int ergebnis = n * zahl;
  return ergebnis;
}

Wo kommt das noch vor?

rekursive Methoden braucht man bei folgenden Themen:

• Rekursion bei Binärbäumen
  Unter anderem werden Inorder- Preorder und Post-Order Traversierungen von Binärbäumen rekursiv programmiert.
• Quicksort

• Tiefendurchlauf bei Graphen

rekursive Datenstrukturen

Binärbäume sind als Datenstruktur rekursiv definiert. Denn jeder Binärbaum enthält seinerseits zwei Binärbäume (den rechten und den linken).