Rekursion

Aus SibiWiki
Zur Navigation springen Zur Suche springen

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:

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).