4. Rekursion

Bei der Rekursion handelt es sich um eine Programmiertechnik, die ein Problem auf ein oder mehrere kleinere Probleme zurückführt. In einer Programmiersprache wie Java umgesetzt äußert sich die Rekursion in einer Java-Methode, die sich selbst aufruft.

Türme von Hanoi

Die Türme von Hanoi sind ein klassisches Beispiel für einen rekursiven Algorithmus. Bei diesem Spiel müssen mehrere verschieden große Scheiben von einem Quellstapel auf einen Zielstapel gebracht werden. Dabei darf aber immer nur eine Scheibe bewegt werden, zudem darf immer nur eine kleinere Scheibe auf einer größeren Scheibe liegen. Das folgende Bild illustriert das Spiel (Quelle Wikipedia):

Eine rekursive Herangehensweise beschreibt die Lösung des Problems folgendermaßen: Wenn du n Scheiben vom Quell- auf den Zielstapel bringen willst, dann verschiebe zunächst n-1 Scheiben auf den Hilfsstapel, dann 1 Scheibe (die unterste) auf den Zielstapel und zum Schluss n-1 Scheiben vom Hilfs- auf den Zielstapel.

Der folgende Java-Algorithmus setzt voraus, dass die drei Stapel mit 1, 2, 3 durchnummeriert sind. Zu Beginn wird die Methode also beispielsweise zur Lösung des 5-Scheiben-Problems mit den Parametern 5, 1, 3, 2 aufgerufen. Die Scheibenbewegungen werden durch Bildschirmausdrucke dargestellt.

public class Hanoi {

    public void TvH(int n, int start, int ziel, int hilf) {

        if (n==1) {
            System.out.println(start+" -> "+ziel);
        }
        else {
            TvH(n-1, start, hilf, ziel);
            TvH(  1, start, ziel, hilf);
            TvH(n-1, hilf,  ziel, start);
        }
    }

}

Für das 5-Scheiben-Problem ergibt sich demnach folgende Ausgabe:

1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
1 -> 2
3 -> 2
3 -> 1
2 -> 1
3 -> 2
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
2 -> 1
3 -> 2
3 -> 1
2 -> 1
2 -> 3
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3

Rekursive Algorithmen

An dieser Stelle werden exemplarisch zwei bekannte rekursive Algorithmen vorgestellt.

Binäre Suche

Als erstes Beispiel wird die binäre Suche auf einem Feld besprochen. Gegenüber der iterativen Lösung wird der Suchraum hier durch den rekursiven Aufruf verkleinert. Zu Beginn wird der Suchvorgang auf dem kompletten Feld in Gang gebracht. Je nach Fall verengt sich der Suchraum in jeder Rekursionsebene, bis entweder das gewünschte Element gefunden wurde oder der Suchraum leer ist (Fall l>r).

public int starteBinaereSucheRekursiv(int[] array, int key) {

    int n = array.length;

    return sucheBinaer(array, key, 0, n-1);    
}

/* Fuehrt die eigentliche binaere Suche durch. */
private int sucheBinaer(int[] array, int key, int l, int r) {

    // Abbruchbedingung fuer erfolglose Suche: l>r
    if (l>r) { return -1; }

    // Bestimme die Mitte des Feldabschnitts
    int m = (l+r) / 2;

    // Unterscheide die drei F?lle

    // 1. Fall: GEFUNDEN
    if (array[m] == key) { 
        return m;
    }

    // 2. Fall: Suche LINKS weiter
    else if (key < array[m]) { 
        return sucheBinaer(array, key, l, m-1);
    }

    // 3. Fall: Suche RECHTS weiter
    else { 
        return sucheBinaer(array, key, m+1, r);
    }

}  

QuickSort

Das Sortierverfahren QuickSort basiert auf einer simplen Idee, die rekursiv elegant umgesetzt werden kann: Bestimme im aktuellen Teilfeld ein vermutlich mittelgroßes Element (Pivot-Element) und ordne nun links vom Pivot alle kleineren und rechts vom Pivot alle größeren Elemente an. Sortiere den linken und rechten Bereich anschließend durch zwei Rekursionsaufrufe.

public void doQuickSort(int[] feld) {

      quickSort(feld,0,feld.length-1);

}

private void quickSort(int[] feld, int l, int r) {  

      if (l>=r) { return; }

      int i, j, m;
      int pivot, hilf;

      // Bestimme Pivotelement
      i = l;
      j = r;
      m = (l+r)/2;
      pivot = feld[m];

      // Teile in zwei Teilfelder
      while (i<=j) {
          while (feld[i]<pivot) { i++; }
          while (feld[j]>pivot) { j--; }
          if (i<=j) { // Tausche Feldinhalte
              hilf = feld[i];
              feld[i] = feld[j];
              feld[j] = hilf;
              i++;
              j--;
          }
      }

      quickSort(feld,i,r);
      quickSort(feld,l,j);

}