Apps für Android programmieren leicht gemacht!
2.7 Rekursion

2.7 Rekursion

Hiermit möchten wir nun die Rekursion ansprechen.
Die Rekursion ist eine Möglichkeit Befehle mehrfach zu durchlaufen und sich somit Programmierarbeit zu sparen. Eigentlich handelt es sich bei der Rekursion um nicht viele mehr, als eine andere Art Schleifen zu implementieren. Schleifen haben wir ja bereits in Kapitel 2.3 angesprochen, allerdings fehlte uns bisher noch das Grundwissen über Methoden und die Lebensdauer von Variablen, weshalb wir die Rekursion erst so spät ansprechen.

Bei der Rekursion handelt es sich um Methoden, die von sich selber immer wieder aufgerufen werden, bis eine bestimmte Abbruchbedingung erfüllt ist.
Wichtig ist aber zu beachten, dass die Methoden so lange am „Leben bleiben“, bis die Abbruchbedingung in der aller letzten Methode erfüllt ist.
Das heißt also, wenn sich eine fiktive Methode „addieren“ insgesamt 4 mal selber aufruft bleibt der erste, zweite und dritte Aufruf „am Leben“, bis der vierte Aufruf dann die Abbruchbedingung enthält und sich nicht noch weiter aufruft.

 

Kleines Beispiel:

Wir machen dazu einfach mal ein kleines Beispiel, damit die Funktionsweise der Rekursion erkenntlich wird.
Als bestes Beispiel könnte man den mathematischen Operator Fakultät nutzen. Das Zeichen für Fakultät ist „!“.
Bei der Fakultät wird der angegebene Startwert mit allen Zahlen die kleiner sind als der Startwert multipliziert, bis man die 1 erreicht.

Fakultät von 4:
4! = 4*3*2*1 = 24

 

Rekursion in Java:

public int fakultaet(int zahl){
   if(zahl == 1){
      return 1;
   }

   return zahl * fakultaet( zahl - 1 );
}


int ergebnis = fakultaet(3);

 

Erklärung:

Was ist dort gerade passiert werden ihr euch sicherlich fragen?
Nun ja, hier muss ich etwas weiter ausholen.
Wie wir uns bereits denken können sollte in der Variable „ergebnis“ nun die Zahl 6 gespeichert sein, da 3*2*1 = 6.

Fangen wir nun an zu erklären, was dort gerade passiert ist.
In Zeile 1-7 haben wir uns eine rekursive Methode geschrieben, dazu gleich mehr.
In Zeile 10 rufen wir das erste mal die Methode „fakultaet“ mit einem Startwert von 3 auf.

 

  1. Wir prüfen nun, ob der übergebene Wert gleich 1 ist, da er 3 ist versuchen wir in Zeile 6 die übergebene Zahl (3) mit dem zu multiplizieren, was bei „fakultaet(2)“ herauskommt. Da wir das Ergebnis von „fakultaet(2)“ aber noch nicht kennen, bleibt „fakultaet(3)“ „am Leben“.
  2. Nun schauen wir uns den Aufruf der Methode „fakultaet(2)“ an.
    Wieder prüfen wir ob der übergebene Wert gleich 1 ist, da er 2 ist versuchen wir in Zeile 6 die übergebene Zahl (2) mit dem zu multiplizieren, was bei „fakultaet(1)“ herauskommt.
  3. Nun schauen wir uns den Aufruf der Methode „fakultaet(1)“ an. Wieder prüfen wir ob der übergebene Wert gleich 1 ist. Dieses mal ist er 1, also geben wir eine 1 zurück, ohne zu multiplizieren. (1 ist unsere Abbruchbedingung und return der Abbruch)
  4. Der Aufruf der Methode „fakultaet(1)“ wird geschlossen.
  5. Jetzt passiert etwas interessantes. Der Aufruf der Methode „fakultaet(2)“ bekommt nun vom Aufruf der Methode „fakultaet(1)“ den Wert 1 zurückgeliefert und kann nun endlich rechnen. Es wird hier 2*1 gerechnet und anschließend das Ergebnis (2) zurückgegeben.
  6. Der Aufruf der Methode „fakultaet(2)“ wird geschlossen.
  7. Nun erhält auch endlich die Methode mit dem Aufruf „fakultaet(3)“ einen Wert der Methode „fakultaet(2)“ zurück und kann 3*2 rechnen. Da wir keine weiteren Rekursionen haben wird nun zum Schluss das Ergebnis an die Variable „ergebnis“ übergeben.
  8. Der Aufruf der Methode „fakultaet(3)“ wird geschlossen.

 

Wie wir feststellen wird die Rekursion vorwärts aufgerufen, aber erst bei der Abbruchbedingung wieder rückwärts abgearbeitet.

 

Das Äquivalent zur Rekursion:

Wie bereits oben angesprochen kann man das Ganze auch mit einer Schleife programmieren.
Hier das Gegenbeispiel:

public int fakultaet(int zahl){
   for(int i = (zahl - 1); i > 0; i--){
      zahl = zahl * i;
   }
   return zahl;
}

int ergebnis = fakultaet(3);

Hier gehen wir den Startwert-1 mal durch die Schleife und multiplizieren jedes mal mit dem momentanen Wert i der Schleife, bis i = 0 ist. Unsere Abbruchbedingung ist, dass i größer 0 sein soll, ab dem Zeitpunkt, an dem i = 0 ist wird die Schleife abgebrochen und es wird ein Wert an „ergebnis“ zurückgeliefert.

Marvin

Ich bin 23 Jahre jung und studiere zurzeit Wirtschaftsinformatik an der Georg-August-Universität in Göttingen. Ich bin ein Mensch, der sich neben der Programmierung noch für tausend andere Dinge interessiert, die mal mehr und mal weniger verrückt sind. Vor allem aber bin ich Feuer und Flamme mit der Programmierung von eigenen kleinen Apps und Programmen, die mein Leben bereichern.

3 Kommentare

*Pflichtfeld

    • Hallo,

      die Funktion bricht immer dann ab, wenn die Zahl 1 erreicht.
      Wenn du also die Funktion mit einer 3 startest, dann ruft sie sich selber mit einer 2 nochmal auf.
      Die Funktion mit der 2 ruft sich selber mit einer 1 nochmal auf.
      Die Funktion mit der 1 beendet sich dann und gibt an die Funktion mit der 2 eine 1 zurück.

      Wenn du die Funktion bereits mit einer 1 startest, dann wird sie sofort beendet und das Ergebnis ist die Rückgabe 1.

      Gruß