13.2 Rekursive Methoden in Java
 
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 noch einmal klar machen, was bei einem rekursiven Aufruf einer Methode passiert.  Wird Zeile #3 abgearbeitet, wir die Methode, beginnend in Zeile #5 gestartet. In Zeile #8 wird, da a nicht 0 ist, die Methode erneut aufgerufen, Zeile #9 ist noch nicht abgearbeitet. Der rekursive Abstieg beginnt. Die Methode ruft sich immer wieder erneut auf. Erst wenn a den Wert 0 hat, der Basisfall ist eingtreten, werden die 'Reste' der noch offenen Methoden im rekursiven Aufstieg abgearbeitet. Die Analogien zu der Chaplin-Filmsequenz sind deutlich. Man kann diese Situation auch in einem sog. Sequenzdiagramm darstellen. 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 rekusion(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.
 
Debugger Schaltet man beim Java-Editor den Debugger ein und lasst das Programm im Trace-Modus (das Programm wird auf Klick Anweisung für Anweisung abgearbeitet) laufen, kann man sehr deutlich die Arbeitsweise der Methoden und die Belegung der Variablen beobachten.

Im Start-Menü lässt sich der Debugger starten.

Über das Menü lässt sich dann über Einzelanweisungen, oder bequemer mit der F7 Taste das Programm im Trace-Modus beobachten


 

[Für die, die den Java-Editor nicht zur Hand haben, lässt sich der Trace-Modus über eine Reihe von Sreenshots nachvollziehen. Klicken Sie dazu auf diese Bemerkung]
 
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 13.3 Der ggT - Version 3: rekursiv
zur Startseite www.pohlig.de  (C) MPohlig 2004