Kleines Nachschlagewerk Informatik
Rekursion
Grundmuster
Ein Selbstaufruf sieht so aus, dass in der Definition der Methode diese selbst aufgerufen wird.

      function berechneIrgendwas(parameter)
          ...
          berechneIrgendwas(veränderte Parameter)
          ...
            
Beispiel Fibonacci-Folge
Die Fibonacci-Folge ist 1 1 2 3 5 8 13 usw.

Sie beginnt mit zwei Einsen. Danach ist jedes Element die Summe der beiden Vorgänger. Eine rekursive Art der Berechnung (es geht auch anders!) wäre:

      int Funktion fibonacci(n)
          wenn n = 1 oder n = 2
              Rückgabe 1
          sonst
              Rückgabe fibonacci(n-1) + fibonacci(n-2)
            
Der Aufrufbaum für fibonacci(5) sei zur Verdeutlichung angegeben.



Teile und Herrsche
Eng mit Rekursion verbunden ist das Prinzip "Teile und Herrsche". Wenn eine Aufgabe zu kompliziert ist, zerlege sie, gib die Teilaufgaben weiter und füge die Ergebnisse zusammen.

Teilaufgaben werden so lange zerlegt, bis sie (einfach) lösbar sind.
Beispiel Quicksort
Ein Array (oder eine Liste) enthält Daten. Diese sollen geordnet werden. Man sucht einen mittleren Wert (Pivot-Element) und teilt die Daten in "Kleine" (kleiner oder gleich dem Pivot-Element) und "Große" (größer als das Pivot-Element).

Dann bittet man um das Sortieren der kleinen und großen Elemente. Dies wird solange fortgeführt, bis das Sortieren einfach ist. Einfach ist es, wenn nur ein Element vorhanden ist.

      Funktion sort alleDaten
          wenn anzahl(alleDaten) = 1
              Rückgabe alleDaten
          sonst
              pivot sucheMedian(alleDaten)
              für wert in alleDaten
                  wenn wert <= pivot
                      wert einfügen in kleineWerte
                  sonst
                      wert einfügen in kleineWerte
              kleineWerte = sort(kleineWerte)
              großeWerte = sort(großeWerte)
              alledaten = kleineWerte + großeWerte
              Rückgabe alleDaten
            
Beispiel Sierpinski-Dreieck




Das Sierpinski-Dreieck besteht aus fortlaufend kleineren Dreiecken, wie das Bild zeigt. Auch dieses lässt sich sehr gut rekursiv zeichnen. Wann ein Dreieck klein ist, kann man gut mit der Rekursionstiefe entscheiden.

      Funktion zeichneDreieck(P1, P2, P3)
          wenn das Dreieck klein ist
              zeichne das Dreieck mit P1, P2, P3
          sonst
              Berechne Mittelpunkte:
              M1 = Mitte von P1 und P2
              M2 = Mitte von P2 und P3
              M3 = Mitte von P3 und P1
              zeichneDreieck(P1, M1, M3)
              zeichneDreieck(M1, P2, M2)
              zeichneDreieck(M3, M2, P3)