Schlichte Rekursion

[Charles Imbusch]

Hallo zusammen,

um mir die schlichte Rekursion konkret vorstellen zu können, habe ich die
Fakultätsfunktion als Beispiel genommen und folgendermaßen implementiert:

public class fakClass2{
static int fak(int r, int i){
if( i == 0 ){
return(r);
}
else{
return(fak(r * i, i - 1));
}
}
static int fak(int n){
return(fak(1, n));
}
}

Als kleines Testprogramm:

public class fakClass2test{
public static void main(String args[]){
for(int i = 0; i < 6; i++)
{
System.out.println(i + ": " + fakClass2.fak(i));
}
}
}

Das Programm liefert mir auch die richtigen Werte (vorrausgesetzt n >= 0).
Meine Frage ist jetzt allerdings, kann ich davon ausgehen, dass
normalerweise immer nur zwei Inkarnationen von fak existieren? Also, wenn
das Ergebnis fertig ist bei der Bedingung i = 0, dann auch wirklich ohne
Umwege zum ursprünglichen Aufrufer zurückgeht?

Leider ist mir keine Idee eingefallen, wie ich das testen könnte, Infos
dazu habe ich leider nicht ausreichend gefunden.

Danke im vorraus,

Charlie

[Frank Buss]

Post by Charles Imbusch
Meine Frage ist jetzt allerdings, kann ich davon ausgehen, dass
normalerweise immer nur zwei Inkarnationen von fak existieren? Also, wenn
das Ergebnis fertig ist bei der Bedingung i = 0, dann auch wirklich ohne
Umwege zum ursprünglichen Aufrufer zurückgeht?

was meinst du mit "Inkarnation" in diesem Zusammenhang? Funktionen werden
nicht wie Objekte angelegt, sodaß also die Funktion nur einmal da ist.
Allerdings wird jeweils ein neuer Stackframe bei jedem erneuten rekursiven
Aufruf angelegt, sodaß der Rücksprung erst alle Stackframes in umgekehrter
Reihenfolge wieder abbaut, bis der Programmablauf wieder beim Aufrufer
angekommen ist.

Post by Charles Imbusch
Leider ist mir keine Idee eingefallen, wie ich das testen könnte, Infos
dazu habe ich leider nicht ausreichend gefunden.

Lade dir Eclipse von http://www.eclipse.org/ (oder eine andere IDE deiner
Wahl, wie Netbeans, IDEA usw.) und gehe deine Anwendung im
Debug-Einzelschrittmodus durch.

[Stefan Ram]

Post by Frank Buss
was meinst du mit "Inkarnation" in diesem Zusammenhang?
Funktionen werden nicht wie Objekte angelegt, sodaß also die
Funktion nur einmal da ist.

Ich denke, daß man dies schon so sehen kann. Die Bezeichnung
"Inkarnation" ist für Operationen in dieser Bedeutung
etabliert. Ungewöhnlich wäre es erst statt von einer
"Inkarnation" von einem "Exemplar" wie bei einer Klasse zu
sprechen, aber selbst das hätte seine Berechtigung, denn:

Objekte kann man als Verallgemeinerung von
Operationsexemplaren ansehen.

Bei einem Aufruf "f()" wird ein Exemplar der Operation "f()"
erstellt. Den Feldern beim Objekt entspricht bei der Operation
der Aktivierungsverbund, hier also Exemplare der lokalen
Variablen. Den Methoden des Objekts entspricht hier nur diese
eine Operation. (Insbesondere bei der Rekursion macht es sich
bemerkbar, daß es mehrere solcher Operationsexemplare
gleichzeitig geben kann.)

Wenn man nun von den Operationen den Weg zu den Abschlüssen
geht, so macht man den ersten Schritt von der Operation zum
Objekt, indem die Lebenszeit nicht mehr nach dem Stapelprinzip
"Zuerst rein - zuerst raus" kontrolliert wird, sondern
nach dem Haldenprinzip beliebig festgelegt werden kann.

Versieht man einen Abschluß dann noch mit mehreren
Operationen, ist man schließlich beim Objekt gelandet.

Post by Frank Buss
Allerdings wird jeweils ein neuer Stackframe bei jedem erneuten
rekursiven Aufruf angelegt, sodaß der Rücksprung erst alle
Stackframes in umgekehrter Reihenfolge wieder abbaut, bis der
Programmablauf wieder beim Aufrufer angekommen ist.

Das, was Du hier "Stackframe" nennst, ist das, was ich
als "Aktivierungsverbund" bezeichne.

Hier seien einmal Schaubilder aus einem meiner Kurse
dargestellt, in dem ich den Begriff "Inkarnation"
veranschauliche (im dritten Schaubild):

Schaubild: Prozedur mit Parameter [Struktogramm]

Prozedurdefinition grüße
Eingangsparameter name
.----------------------------------.
|Drucke "Hallo " |
|----------------------------------|
|Drucke name |
|----------------------------------|
|Drucke "!" |
|----------------------------------|
|Drucke das Zeilenende. |
'----------------------------------'
Klient
.----------------------------------.
|Prozeduraufruf grüße |
| Argument "Sabine" |
|----------------------------------|
|Prozeduraufruf grüße |
| Argument "Andreas" |
'----------------------------------'

Ausgabe
Hallo Sabine!
Hallo Andreas!

Schaubild: Aufruf einer Prozedur mit Argument [Kompassdiagramm]

.-----------------------.
| Parameter Prozedur |
------------->| name grüße |
"Sabine" '-----------------------'
Argument |
V
Ausgabe "Hallo Sabine!" (Verhalten, Wirkung)

.-----------------------.
| Parameter Prozedur |
------------->| name grüße |
"Andreas" '-----------------------'
Argument |
V
Ausgabe "Hallo Andreas!" (Verhalten, Wirkung)


Schaubild: Zeitlicher Ablauf bei Aufruf einer Parameterprozedur

|
| Klient
| .----------------------.
| | | Erste Inkarnation
| | | der Parameterprozedur
| | gruesse( "Sabine" ) | "gruesse"
| | | .-------------------.
| | | | ( text parameter | Anfang der
| | '--------> name ) | Lebenszeit von
| | | Drucke "Hallo " | "name"
| | | Drucke name |
| | | Drucke "!" |
| | | Drucke Zeilenende |
| | '-------------------' Ende der
| | | Lebenszeit von
| | | "name"
| | | Zweite Inkarnation
| | | der Parameterprozedur
| | gruesse( "Andreas" ) | "gruesse"
| | | .-------------------.
| | | | ( text parameter | Anfang der
| | '--------> name ) | Lebenszeit von
| | | Drucke "Hallo " | "name"
| | | Drucke name |
| | | Drucke "!" |
| | | Drucke Zeilenende |
| | '-------------------' Ende der
| | | Lebenszeit von
| | | "name"
| | |
| '----------------------'
|
V Zeit

Bei der Rekursion existieren dann mehrere Inkarnationen
einer Operation gleichzeitig.

Dieses Thema behandle ich in der folgenden Lektion für Java
ebenfalls unter Verwendung des Wortes "Inkarnation", leider
aber noch ohne Schaubilder.

http://www.purl.org/stefan_ram/pub/java_traegheit_de

[Michael Paap]

Post by Charles Imbusch
um mir die schlichte Rekursion konkret vorstellen zu können, habe ich die

[Code]

Hallo Charles,

zunächst mal würde ich dir empfehlen, dich an die üblichen
Java-Konventionen zu halten, das macht deinen Code lesbarer für alle. Also :

- Klassennamen immer groß beginnen, beim Beginn neuer Wörter in
Bezeichnern wieder ein Großbuchstabe.
- öffnende Blockklammern in die gleiche Zeile wie for bzw. if
- else hinter die schließende Klammer des if
- weg mit den unnötigen Klammern um den return-Wert
- kein else, wenns nicht nötig ist

Etwa so:

public class FakClass2 {
static int fak(int r, int i) {
if (i == 0) {
return r;
}
return fak(r * i, i - 1);
}

static int fak(int n) {
return fak(1, n);
}
}

Post by Charles Imbusch
Das Programm liefert mir auch die richtigen Werte (vorrausgesetzt n >= 0).

Aber mit unnötigen Verrenkungen... im Grund ist das keine Rekursion,
sondern eine umständlich verpackte Iteration... was wohl auch das ist,
was du willst. Du schleppst eine zusätzliche Variable für den aktuellen
Zwischenwert mit. Wenn dud ie weglässt, entspricht das, was du da
schreibst, imho etwa:

public class FakClassX {

static int zwischenSumme;

static void fakt (int i) {
if (i == 0) {
return;
}
zwischenSumme *= i;
fakt(i - 1);
}

static int fak(int n) {
zwischenSumme = 1;
fakt(n);
return zwischenSumme;
}
}

Post by Charles Imbusch
Meine Frage ist jetzt allerdings, kann ich davon ausgehen, dass
normalerweise immer nur zwei Inkarnationen von fak existieren?

Meinst du damit, dass immer nur zwei Methodenaufrufe auf dem Stack
liegen? Nein. Du legst n + 1 Aufrufe von fak(int, int) auf den Stack.

Post by Charles Imbusch
Also, wenn
das Ergebnis fertig ist bei der Bedingung i = 0, dann auch wirklich ohne
Umwege zum ursprünglichen Aufrufer zurückgeht?

Nein. Es muss die ganze Kette rückwärts aufgewickelt werden.

Post by Charles Imbusch
Leider ist mir keine Idee eingefallen, wie ich das testen könnte, Infos
dazu habe ich leider nicht ausreichend gefunden.

Du könntest an der "tiefsten" Stelle eine Exception werfen und dir den
Stacktrace ansehen:

public class FakClass2 {
static int fak(int r, int i) {
if (i == 0) {
throw new RuntimeException();
}
return fak(r * i, i - 1);
}

static int fak(int n) {
return fak(1, n);
}
}

Wenn du das so aufrufst:

public class FakClass2Test {
public static void main(String args[]) {
System.out.println("6 : " + FakClass2.fak(6));
}
}

erhältst du:

Exception in thread "main" java.lang.RuntimeException
at FakClass2.fak(FakClass2.java:4)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:10)
at FakClass2Test.main(FakClass2Test.java:3)

Eine "richtige" rekurive Berechnung sähe z.B. so aus:

public class FakClassR {
static int fak(int r) {
if (r == 0) {
return 1;
}
return r * fak(r - 1);
}
}

Aber das ist dir vermutlich klar.

Gruß,
Michael Paap

[Michael Paap]

Post by Charles Imbusch
um mir die schlichte Rekursion konkret vorstellen zu können, habe ich die

[Code]

Hallo Charles,

zunächst mal würde ich dir empfehlen, dich an die üblichen
Java-Konventionen zu halten, das macht deinen Code lesbarer für alle. Also :

- Klassennamen immer groß beginnen, beim Beginn neuer Wörter in
Bezeichnern wieder ein Großbuchstabe.
- öffnende Blockklammern in die gleiche Zeile wie for bzw. if
- else hinter die schließende Klammer des if
- weg mit den unnötigen Klammern um den return-Wert
- kein else, wenns nicht nötig ist

Etwa so:

public class FakClass2 {
static int fak(int r, int i) {
if (i == 0) {
return r;
}
return fak(r * i, i - 1);
}

static int fak(int n) {
return fak(1, n);
}
}

Post by Charles Imbusch
Das Programm liefert mir auch die richtigen Werte (vorrausgesetzt n >= 0).

Im Grund ist das keine Rekursion, sondern eine als Rekursion verpackte
Iteration... was wohl auch das ist, was du willst. Wenn du die
mitgeschleppte Variable für den Zwischenwert weglässt, entspricht das,
was du da schreibst, ja etwa:

public class FakClassX {

static int zwischenWert;

static void fakt (int i) {
if (i == 0) {
return;
}
zwischenWert *= i;
fakt(i - 1);
}

static int fak(int n) {
zwischenWert = 1;
fakt(n);
return zwischenWert;
}
}

Im Grunde ist das keine sinnvolle Rekursion, weil der Rückgabewert nicht
verarbeitet wird. Eben dies meinst du wohl mit "primitiver Rekursion"

Post by Charles Imbusch
Meine Frage ist jetzt allerdings, kann ich davon ausgehen, dass
normalerweise immer nur zwei Inkarnationen von fak existieren?

Meinst du damit, dass immer nur zwei Methodenaufrufe auf dem Stack
liegen? Nein. Du legst n + 1 Aufrufe von fak(int, int) auf den Stack.

Post by Charles Imbusch
Also, wenn
das Ergebnis fertig ist bei der Bedingung i = 0, dann auch wirklich ohne
Umwege zum ursprünglichen Aufrufer zurückgeht?

Nein. Es muss die ganze Kette rückwärts aufgewickelt werden.

Post by Charles Imbusch
Leider ist mir keine Idee eingefallen, wie ich das testen könnte, Infos
dazu habe ich leider nicht ausreichend gefunden.

Du könntest an der "tiefsten" Stelle eine Exception werfen und dir den
Stacktrace ansehen:

public class FakClass2 {
static int fak(int r, int i) {
if (i == 0) {
throw new RuntimeException();
}
return fak(r * i, i - 1);
}

static int fak(int n) {
return fak(1, n);
}
}

Wenn du das so aufrufst:

public class FakClass2Test {
public static void main(String args[]) {
System.out.println("6 : " + FakClass2.fak(6));
}
}

erhältst du:

Exception in thread "main" java.lang.RuntimeException
at FakClass2.fak(FakClass2.java:4)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:6)
at FakClass2.fak(FakClass2.java:10)
at FakClass2Test.main(FakClass2Test.java:3)

Eine "richtige" rekurive Berechnung sähe z.B. so aus:

public class FakClassR {
static int fak(int r) {
if (r == 0) {
return 1;
}
return r * fak(r - 1);
}
}

Aber das ist dir vermutlich klar.

Gruß,
Michael Paap

[Wanja Gayk]

Michael Paap said...

Post by Michael Paap
Im Grund ist das keine Rekursion, sondern eine als Rekursion verpackte
Iteration... was wohl auch das ist, was du willst. Wenn du die
mitgeschleppte Variable für den Zwischenwert weglässt, entspricht das,
public class FakClassX {
static int zwischenWert;
static void fakt (int i) {
if (i == 0) {
return;
}
zwischenWert *= i;
fakt(i - 1);
}

Vorsicht, das ist ganz böser code und auch _nicht_ das gleiche!
Wen man den zwischemwert mitschleift, dann langet der Zwischenwert auf
dem Stack, bei dem obigen Code passiert das nicht und genau das ist das
Problem: Wenn zwei Threads auf die Klasse zugreifen kommt möglicherweise
ganz, ganz viel Unsinn raus, weil die fakt-Methode von der statischen
Variable zwischenWert abhängt, besser man schleift die mit!

Post by Michael Paap
public class FakClassR {
static int fak(int r) {
if (r == 0) {
return 1;
}
return r * fak(r - 1);
}
}

Diesen Code würde ich übigens bevorzugen.

Gruß,
-Wanja-

[Stefan Matthias Aust]

[f n = f (n - 1) * n | f 0 = 0]
Diesen Code würde ich übigens bevorzugen.

Nun, das, was hier als schlichte Rekursion durch den Thread geistert,
ist eigentlich vorzusiehen, denn es kann derart implementiert werden,
dass die Aktivierungen (stack frames, activation records) der Funktionen
wiederverwendet werden können, also gar keine "echte" Rekursion benutzt
werden muss. Trotzdem folgt des dem Rekursions-Entwurfsmuster und ist
damit technisch sauber und formal interessanter als Schleifen.
Rekursionen lassen sich einfacher per vollständiger Induktion beweisen,
bei Schleifen muss man mit Invarianten arbeiten und so so quasi die
Rekursion selbst ableiten.

Ich kenne die "schlichte" Rekursion unter dem Begriff "Endrekursion" und
ein solcher rekursiver wird auch tail call genannt. Siehe dann tail
recursion als Stichwort.

Einige Sprachen (die meisten funktionalen Sprachen, Scheme ist das
prominenteste Beispiel, aber auch Lua 5 wie ich gerade gelernt habe)
fordern, dass Endrekursion derart implementiert werden muss, dass der
Stack niemals überläuft.

Java hat keine solche Forderung. Bei C# weiss ich es nicht, aber die
.NET-VM hat zumindest im Gegensatz zur JVM einen Maschinenbefehl für
eine tail call, sodass man derartige Forderungen effizient umsetzen kann.

[Michael Paap]

Post by Wanja Gayk
Vorsicht, das ist ganz böser code

Das sowieso.

Post by Wanja Gayk
und auch _nicht_ das gleiche!

[Mutithreading]

Ok, derlei Aspekte hatte ich jetzt ganz draußen gelassen, weils eh böser
Code ist. ;-)

Post by Wanja Gayk

Post by Michael Paap
public class FakClassR {
static int fak(int r) {
if (r == 0) {
return 1;
}
return r * fak(r - 1);
}
}

Diesen Code würde ich übigens bevorzugen.

In der Praxis? Bitte nicht... da sollte man derlei denn doch iterativ lösen.

Gruß,
Michael

[Charles Imbusch]

Post by Michael Paap
Hallo Charles,

Hallo Michael

Post by Michael Paap
zunächst mal würde ich dir empfehlen, dich an die üblichen

Gut, ich versuche mich dran zu gewöhnen ;)

Post by Michael Paap
- Klassennamen immer groß beginnen, beim Beginn neuer Wörter in
Bezeichnern wieder ein Großbuchstabe.

Ja, die Sache mit den BinnenMajuskeln...

Post by Michael Paap
- öffnende Blockklammern in die gleiche Zeile wie for bzw. if

Hatte ich doch, oder?

Post by Michael Paap
- else hinter die schließende Klammer des if - weg mit den unnötigen
Klammern um den return-Wert - kein else, wenns nicht nötig ist

ACK, wenns so Gang und Gebe ist.

Post by Michael Paap
Im Grund ist das keine Rekursion, sondern eine als Rekursion verpackte
Iteration... was wohl auch das ist, was du willst.

Genau.

Post by Michael Paap

Post by Charles Imbusch
Also, wenn
das Ergebnis fertig ist bei der Bedingung i = 0, dann auch wirklich
ohne Umwege zum ursprünglichen Aufrufer zurückgeht?

Nein. Es muss die ganze Kette rückwärts aufgewickelt werden.

Das ist rein theoretisch ja nicht notwendig die komplett rückwärts
aufzuwickeln. Durch die Hinweise konnte ich auch mehr googeln und Java
scheint schlichte-/repetitive Rekursion oder tail call nicht zu
unterstützen. Es bleibt also bei Java nichts anderes übrig sowas
iterativ zu machen, wenn es effizient sein soll. Was mich auch nicht
stört, es ging mir darum rauszufinden, ob Java dazu in der Lage ist.

Post by Michael Paap
Du könntest an der "tiefsten" Stelle eine Exception werfen und dir den

Danke, hilfreiche Idee.
[Code]

Wie schon erwähnt, es ging mir nicht um die Funktion, sondern um Java.

Danke für die Antworten auch von den andern Postern!

Gruß,
Charlie

[Stefan Matthias Aust]

Post by Charles Imbusch
aufzuwickeln. Durch die Hinweise konnte ich auch mehr googeln und Java
scheint schlichte-/repetitive Rekursion oder tail call nicht zu
unterstützen. Es bleibt also bei Java nichts anderes übrig sowas

Nein, Java muss es (aufgrund der Spezifikation) nicht unterstützen, aber
eine JVM könnte diese Optimierung vornehmen. Wenn, dann wird es wohl
Hotspot-Server machen. Probiere das doch einfach mal für eine Fakultät
von 30.000 oder so aus. Das Ergebnis wird natürlich nicht stimmen, weil
die int (oder auch longs) schon längst übergelaufen sind, aber spannend
wäre, ob es zu stack overflow fehlern kommt oder nicht. Mögliche
Kandidaten zum Ausprobieren wären

- hotspot client
- hotspot server (hotspot ist Suns JVM)
- jrockit
- IBM's freie JVM für Linux
- J9 (auch von IBM)
- GIJ (GNUs Java-Interpreter)
- GCJ (Java per GCC kompiliert)
- Excelsior JET (noch ein AOT-Compiler)
- IKVM unter MS .NET
- IKVM unter Mono (ikvm ist ein Übersetzer nach .NET)

Post by Charles Imbusch

Post by Michael Paap
Du könntest an der "tiefsten" Stelle eine Exception werfen und dir den

Danke, hilfreiche Idee.

Nicht unbedingt. Eine JVM könnte erkennen, dass eine Exception geworfen
werden könnte und daher auf eine sonst durchgeführte Optimierung
verzichten, damit der Stacktrace auch so aussieht, wie man das erwarten
würde.

[Charles Imbusch]

Post by Stefan Matthias Aust
Nein, Java muss es (aufgrund der Spezifikation) nicht unterstützen, aber
eine JVM könnte diese Optimierung vornehmen.

[...]

Post by Stefan Matthias Aust
- hotspot client
- hotspot server (hotspot ist Suns JVM)
- jrockit
- IBM's freie JVM für Linux
- J9 (auch von IBM)
- GIJ (GNUs Java-Interpreter)
- GCJ (Java per GCC kompiliert)
- Excelsior JET (noch ein AOT-Compiler)
- IKVM unter MS .NET
- IKVM unter Mono (ikvm ist ein Übersetzer nach .NET)

Puh, ist ja eine ganz schöne Liste. Werde ich mal ausprobieren, man lernt
ja nie aus.

Post by Stefan Matthias Aust

Post by Michael Paap
Du könntest an der "tiefsten" Stelle eine Exception werfen und dir den

Nicht unbedingt. Eine JVM könnte erkennen, dass eine Exception geworfen
werden könnte und daher auf eine sonst durchgeführte Optimierung
verzichten, damit der Stacktrace auch so aussieht, wie man das erwarten
würde.

Okay, dann also doch mit irgendeiner IDE debuggen.

Gruß,
Charlie


--

[Stefan Matthias Aust]

Post by Charles Imbusch

Post by Stefan Matthias Aust

Post by Michael Paap
Du könntest an der "tiefsten" Stelle eine Exception werfen und dir den

Nicht unbedingt. Eine JVM könnte erkennen, dass eine Exception geworfen
werden könnte und daher auf eine sonst durchgeführte Optimierung
verzichten, damit der Stacktrace auch so aussieht, wie man das erwarten
würde.

Okay, dann also doch mit irgendeiner IDE debuggen.

Im Debug-Modus wird die VM sehr wahrscheinlich auf derartige
Optimierungen verzichten, um die erwarteten Stack-Frames zu liefern.