13.2 Rekursive Methoden in Java |
|
Beispiel Download: RekursionsDemo. java |
#1
public class RekursionDemo{ |
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
|
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 |