14 Weitere rekursive Methoden
14.1 Was passiert bei einer rekursiven Methode?
Beispiel
Download:
RekursionsDemo. java		 
#1  public class RekursionDemo{
#2    public static void main(String[] args){
#3        rekursion(5);
#4    }
#5    private static void rekursion(int a){
#6        a--;
#7        System.out.println(a);
#8        if (a!=0) rekursion(a);
#9        System.out.println(a);
#10   }
#11 }
Ausgaben Die Ausgabe verstehen wir erst, wenn wir uns klar machen, was bei einem rekursiven Aufruf einer Methode passiert.  Wird Zeile #3 abgearbeitet, wir die Methode, beginnend in Zeile #5 gestartet. In Zeile #9 wird, da a nicht 0 ist, die Methode erneut aufgerufen. Zeile #9 ist noch nicht abgearbeitet. Die Methode wird erneut aufgerufen. Erst wenn a den Wert 0 erreicht hat, werden die 'Reste' der noch offenen Methoden abgearbeitet. Man kann diese Situation in einem sog. Sequenzdiagramm. Der Bediener startet das Programm. Die "Lebenslinien" sind gestrichelte Linien nach unten. Der Aufrufen von RekursionsDemo startet die Operation rekursion(), die selbst solange wieder rekursion() aufruft, bis die Abbruchbedingung erfüllt ist. Wie sieht das Szenario in unserem Fall aus, wenn der Startwert für a = 5 ist. Wo wird System.out.println(..) aufgerufen?  
Sequenzdiagramm

 

Das oben dargestellte Diagramm lehnt sich an die Notation der UML (Unified Modeling Language) an. Das Diagramm ist leicht lesbar, für jemanden, der rekursive Algorithmen gewohnt ist. Da wir mit dem Aufruf rekursiver Methoden noch nicht so vertraut sind, wollen wir in der Darstellung noch etwas weiter gehen1).

Deutlich erkennt man, dass der Aufruf von rekursion(4) erst abgeschlossen werden kann, wenn rekursion(3) abgeschlossen ist. rekursion(3) ist seinerseits erst abgeschlossen, wenn rekusrion(2) angeschlossen ist. etc. Es muss also einen 'Punkt' geben, wo der Abstieg zum Aufstieg umkehrt. Die System.out.println(..) sind so in der Methode platziert, dass die erste Ausgabe beim Abstieg und die zweite bei Aufstieg aufgerufen wird. Die Ausgabewerte sind in der Grafik (s.o.) in eckigen Klammern.
   
Fußnoten 1) Diese Darstellung erleichtert am Anfang das Verständnis ist aber unpraktisch, denn beim Einstieg in eine Rekursion ist i.a. nicht bekannt wie groß die Rekursionstiefe, also die Anzahl der rekursiven Aufrufe ist. [zurück]

 
zu 14.2 Fakultät-rekursiv
zur Startseite www.pohlig.de (C) MPohlig 2003