Rekursion

Ein rekursiver Algorithmus oder Programm ist ein Alorithmus oder Programm, welches sich selber direkt oder indirekt aufruft. Jede Rekursion kann theoretisch durch eine Schleife ersetzt werden und umgekehrt, jedoch ist dies nicht immer ratsam. Schleifen und Rekursionen sind also semmantisch äquivalent. Rekursion kommt vom lateinischen Wort recurrere, was zurücklaufen bedeutet.

Erstes Beispiel für eine Rekursion

Fakultät von n

Eingabe: Eine natürliche Zahl n
Ausgabe: Die Fakultät von n
Vorgehensweise:
   Wenn n gleich 0,
   dann gib 1 zurück,
   ansonsten gib das Produkt von n und dem Algorithmus mit der Eingabe n-1 zurück.

Ausführung des Beispiels mit n = 3

Aufbau des Rekusionsbaums ("Hinweg")

Ebene: n = 3
Ausführung: n ist ungleich 0, berechne daher das Produkt von 3 und (3-1)!
Aufruf: Fakultät(2)

  Ebene: n = 2
  Ausführung: n ist ungleich 0, berechne daher das Produkt von 2 und (2-1)!
  Aufruf: Fakultät(1)

    Ebene: n = 1
    Ausführung: n ist ungleich 0, berechne daher das Produkt von 1 und (1-1)!
    Aufruf: Fakultät(0)

      Ebene: n = 0
      Ausführung: n ist nun gleich 0, gib also 1 zurück
    
Auslösung des Rekusionsbaums ("Rückweg")
    
      Rückgabe: Fakultät(0) = 1
    
    Ebene: n = 1
    Rückgabe: 1 * 1 = 1
  
  Ebene: n = 2
  Rückgabe: 2 * 1 = 2

Ebene: n = 3
Rückgabe: 3 * 2 = 6

Aufbau einer Rekursion

Jede Rekursion besteht aus einer Abbruch-/Terminierungsbedingung und einem Rekusionsrumpf. Der Rekusionsabbruch erfolgt, wenn die Terminierungsbedingung erfüllt ist. Diese Bedingung überprüft, ob die untereste Ebene des Rekusionsbaums errreicht wurde. Im obigen Beispiel ist dies die Überprüfung, ob n gleich 0 ist, da 0! gleich 1 ist. Sollte diese Bedingung nicht erfüllt werden, wird der Rekusionsrumpf ausgeführt. Im Rekursionsrumpf geschieht der Aufruf der Funktion für eine niedrigere Ebene und die Berechnung des Ergebnisses der aktuellen Ebene mit diesem. In dem Beispiel ist dies der Ansonsten-Pfad. Wichtig für eine funktionierenden Rekursion ist, dass die Bedingung irgendwann erreciht wird, da ansonsten die Rekusion nicht terminiert, s. Endlosrekursion.

Zweites Beispiel

Ist die Zahl n grade?

1. Funktion
Eingabe: Eine natürliche Zahl n
Ausgabe: Ja, wenn n gerade ist, Nein, wenn n ungerade ist.
Vorgehensweise:
     Wenn n gleich 0 ist, dann gebe Ja zurück,
     ansonsten gebe das Ergebnis der 2. Funktion für n-1 zurück.

2. Funktion
Eingabe: Eine natürliche Zahl n
Ausgabe: Ja, wenn n ungerade ist, Nein, wenn n gerade ist. 
Vorgehensweise:
     Wenn n gleich 0 ist, dann gebe Nein zurück,
     ansonsten gebe das Ergebnis der 1. Funktion mit n-1 zurück.

Ausführung des zweiten Beispiels mit n = 5

Aufbau des Rekursionsbaums ("Hinweg")

1. Funktion wird mit n = 5 aufgerufen
n ist ungleich 0, daher führe 2. Funktion mit n = 4 aus
  
  2. Funktion mit n = 4
  n ist ungeleich 0, daher führe 1. Funktion mit n = 3 aus

    1. Funktion mit n = 3
    n ist ungleich 0, daher führe 2. Funktion mit n = 2 aus

      2. Funktion mit n = 2
      n ist ungleich 0, daher führe 1. Funktion mit n = 1 aus
        
        1. Funktion mit n = 1
        n ist ungleich 0, daher führe 2. Funktion mit n = 0 aus
       
          2. Funktion mit n = 0
          n ist gleich 0, daher
          Rückgabe: Nein

Auflösung des Rekursionsbaums ("Rückweg")

          1. Funktion mit n = 1
          Rückgabe: Nein

        2. Funktion mit n = 2
        Rückgabe: Nein
  
      1. Funktion mit n = 3
      Rückgabe: Nein

   2. Funktion mit n = 4
   Rückgabe: Nein

1. Funktion mit n = 5
Rückgabe: Nein

=> 5 ist ungrade

Direkte und indirekte Rekursion

Bei der direkten Rekursion wird die Rekursion direkt aufgerufen, indem bei der Rückgabe die Funktion sich selber wieder aufgerufen wird. Beispiel 1 ist zum Beispiel eine direkte Rekursion. Bei der indirekten Rekursion wird die Rekursion indirekt aufgerufen, indem diese Funktion f eine andere Funktion g aufruft, die wiederum f aufruft.