[Tutorial] Rekursion

[Flown]

Was ist eine Rekursion?
Einfach gesagt: Eine Methode die sich selbst aufruft.
Eine Rekursion ist auch, wenn sich mehrere Methoden gegenseitig aufrufen (z.B.: A -> B <-> C).

Wie baut man eine Rekursion?
Das Allerwichtigste, bei einer Rekursion, ist die Abbruchbedingung. Dies muss an der ersten Stelle der Methode verarbeitet werden!

Wenn das nicht geschehen sollte, kommen Endlosrekursionen auf und sprengen somit den Java Methoden Stack.

Bsp.: Schritt für Schritt
Fibonacci ist definiert durch:

f(n) = f(n-1) + f(n-2) für n > 2
f(1) = f(2) = 1

Das heißt wir fangen mit unserer Methode den Fall mit einer Exception ab, dass n < 1 sein kann.

Danach die wirkliche Abbruchbedingung für die Fälle n = 1 und n = 2. Wenn n einen der beiden Werte annimmt, gibt die Funktion laut Definition den Wert 1 zurück.
Mit dieser kleinen Abfrage (und natürlich der Definition) haben wir den ersten Schritt für die Terminierung der Rekursion geschaffen.

public static long fib(int n) {
  if (n < 1) {
    throw new IllegalArgumentException("n must be at least greater than 0.");
  }
  if (n <= 2) {
    return 1;
  }
}

Als nächstes müssen wir sicherstellen, dass wenn nicht der Basis-Fall(n=1 oder n=2) eintritt, die Methode mit kleiner werdendem n neu aufgerufen wird. Laut Definition f(n-1) und f(n-2). In Programm sieht das dann so aus:

public static long fib(int n) {
  if (n < 1) {
    throw new IllegalArgumentException("n must be at least greater than 0.");
  }
  if (n <= 2) {
    return 1;
  } else {
    return fib(n-1) + fib(n-2);
  }
}

Iteration <-> Rekursion

Was man auf alle Fälle wissen sollte ist, dass man jede Rekursion in eine Iteration und umgekehrt wandeln kann. Das wiederum heißt nicht, dass sie gleich komplex sind! Manche Funktionen (siehe Fibonacci-Folge) ist rekursiv intuitiver als iterativ.

Um zu zeigen, wie einfach man Iterationen in Rekursionen umwandeln kann, wird die größte Zahl aus einem Array errechnet.

Iterativ:

public static int max(int[] array) {
  if (array == null || array.length == 0) {
    throw new IllegalArgumentException("Array must not be null or empty.");
  }
  int max = array[0];
  for (int i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }
  return max;
}

Rekrusiv:
Als erstes bauen wir eine Fassade, die die echte Rekursion, mit den richtigen Parametern, startet. Das heißt die Rekursion, weiß nicht an welcher Stelle sie im Array gerade ist, darum muss eine Positionsvariable und das aktuelle Maximum hinzugefügt werden (analog zu dem int i in der for-Schleife und dem max).

public static int max2(int[] array) {
  if(array == null || array.length == 0) {
    throw new IllegalArgumentException("Array must not be null or empty.");
  }
  return maxRec(array, 1, array[0]);
}

Wie bei der iterativen Lösung beginnt der Durchlauf an der Position 1 und das Maximum wird mit dem ersten Wert aus dem Array initialisiert.
Als nächstes bauen wir die Rekursion. Wieder fängt man mit der Abbruchbedingung an! Diese ist erreicht, wenn i >= Länge des Arrays ist (genauer genommen i == Länge des Arrays).

Wenn das Ende noch immer nicht erreicht ist, dann vergleiche max und die aktuelle Position im Array und gib das neue Maximum der nächsten Rekursion mit.

array = [0, 1, 2, 3]
max2 ->
maxRec(array, 1, 0)
-maxRec(array, 2, 1)
--maxRec(array, 3, 2)
---maxRec(array, 4, 3)
----maxRec(array, 5, 3) : return 3
--- return 3
-- return 3
- return 3
return 3

private static int maxRec(int[] array, int i, int max) {
  if (i >= array.length) {
    return max;
  } else {
    return maxRec(array, i + 1, array[i] > max ? array[i] : max);
  }
}

Kleiner Hinweis: Sowas nennt man auch eine Endrekursion, da die letzte Anweisung ein Rekursionsaufruf ist. Manche Sprachen können so etwas optimieren, Java jedoch nicht!

Hier noch einmal das ganze Beispiel:

public class RecursionTutorial {
 
  public static void main(String... args) {
    int[] array = new int[4];
    for (int i = 0; i < array.length; i++) {
      array[i] = i;
    }
    System.out.println(max(array));
    System.out.println(max2(array));
  }
 
  // Iterativ
  public static int max(int[] array) {
    if (array == null || array.length == 0) {
      throw new IllegalArgumentException("Array must not be null or empty.");
    }
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
      if (array[i] > max) {
        max = array[i];
      }
    }
    return max;
  }
 
  // Rekursiv
  public static int max2(int[] array) {
    if (array == null || array.length == 0) {
      throw new IllegalArgumentException("Array must not be null or empty.");
    }
    return maxRec(array, 1, array[0]);
  }
 
  private static int maxRec(int[] array, int i, int max) {
    if (i >= array.length) {
      return max;
    } else {
      return maxRec(array, i + 1, array[i] > max ? array[i] : max);
    }
  }
}

Wenn man jetzt genauer hinsieht, stellt man fest, dass man den Parameter max gar nicht benötigt. Das liegt daran, dass bei jedem Methodenaufruf auch ein Rückgabewert existiert (auch void ist ein Rückgabewert - der eben "nichts" bedeutet).
Als nächstes bauen wir die "optimierte" Rekursion. Wieder fängt man mit der Abbruchbedingung an! Dieses Mal brechen wir ab, wenn wir das letzte Element im Array erreicht haben und geben dieses Element zurück.

Wenn es nicht das letzte Element im Array ist, dann rufen wir die Methode mit nächster Position auf. Ist die letzte Position erreicht wird danach das Maximum, ausgehend vom letzten Element, berechnet und zurückgegeben.

private static int maxRec(int[] array, int i) {
  if(i == array.length - 1) {
    return array[i];
  } else {
    int previousMax = maxRec(array, i+1);
    return previousMax < array[i] ? array[i] : previousMax;
  }
}

Divide & Conquer

Dies ist ein Thema, dass zur Vervollständigung von Rekursionen angefügt ist. Das heißt, es ist ein eigener Bereich, der sich die Rekursion als Hauptwerkzeug hält.
Wichtige Beispiele hierfür sind Sortieralgorithmen, wie Quicksort und Mergesort.