StackOverflowError bei Rekursion verhindern

[Schandro]

Hi,

ich hab ne Rekursion geschrieben, die sich extrem oft selbst aufruft, weswegen ich einen StackOverflowError bekomme. Es ist von mir aber gewollt, das die rekursion so tief geht und es gibt mmn. auch keinen anderen Weg, die Methode zu schreiben...
Gibt es eine Möglichkeit, Java zu sagen, dass er für einen bestimmten Aufruf keinen Stack schreiben soll?

 

[tfa]

Nein, gibt es nicht. Dann würde ja gar nichts mehr funktionieren. Aber du kannst mit -Xss die Stackgröße erhöhen.
Sicher, dass du keine Endlosschleife gebaut hast?

 

[EgonOlsen]

Gibt es eine Möglichkeit, Java zu sagen, dass er für einen bestimmten Aufruf keinen Stack schreiben soll?

Der Stack wird doch für die Rekursion benötigt. Nur wenn du keine Übergabeparameter hättest, hättest du keinen Stack...aber auch keinerlei Rekursion. Du kannst jede Rekursion auch Nicht-Rekursiv bauen. Erfordert je nach Problem etwas Überlegung, aber geht immer. Dann entfällt das Problem mit dem Stack.

 

[maki]

Xss ist der richtige Tipp, allerdings gibt es einen Bug unter Windows: http://www.java-forum.org/de/viewtopic.php?t=67488&highlight=xss


edit SlaterB:
aktueller Link wahrscheinlich:
http://www.java-forum.org/allgemeine-java-themen/64258-rekursion-und-stackoverflow.html

bzw. führt letzlich zu
Bug ID: 4689767 main thread stack size not the same as other threads on all platforms (-Xss<N>)

 

[musiKk]

es gibt mmn. auch keinen anderen Weg, die Methode zu schreiben...

Man kann jede Rekursion auch als Iteration umschreiben. Muss natürlich nicht immer elegant oder einfach sein.

Gibt es eine Möglichkeit, Java zu sagen, dass er für einen bestimmten Aufruf keinen Stack schreiben soll?

Wie schon geschrieben wurde, geht das nicht. Es geht mit Compilern, die Endrekursion (tail recursion) unterstützen, aber die Java-Compiler gehören nicht dazu.

 

[Schandro]

ok, danke für die Tipps. Ich werd versuchen es iterativ umzuschreiben, kann halt nur ein bisschen länger dauern bis ich das hinkriege^^.

 

[tfa]

Gibt es eine Möglichkeit, Java zu sagen, dass er für einen bestimmten Aufruf keinen Stack schreiben soll?

Wie schon geschrieben wurde, geht das nicht. Es geht mit Compilern, die Endrekursion (tail recursion) unterstützen, aber die Java-Compiler gehören nicht dazu.

Kannst du näher erläutern, was du damit meinst? Warum unterstützen Java-Compiler keine Endrekursion? Warum braucht man dann keinen Stack?

 

[SlaterB]

hier
http://de.wikipedia.org/wiki/Endrekursion
steht was im ersten Unterabsatz

 

[tfa]

Achso, es geht um die automatische Umwandlung endrekursiver Methoden in Iteration. Das war vielleicht etwas dumm ausgedrückt.

 

[musiKk]

Warum unterstützen Java-Compiler keine Endrekursion?

Ok, es scheint doch eher mit den JVMs zusammenzuhängen. Bei LtU wird da ein wenig drüber diskutiert.

Das war vielleicht etwas dumm ausgedrückt.

Von wem?
Falls du mich meinst: Endrekursion ist ein gängiges Konzept in Compilern vor allem funktionaler Sprachen (aber auch der GCC produziert bei eingeschalteter Optimierung Code, der Endrekursion berücksichtigt). Auch nach der Erklärung des Begriffs hätte man nicht lange suchen müssen.
Andernfalls will ich nichts gesagt haben.

 

[tfa]

Der Begriff Endrekursion ist mir schon bekannt. Deine (verkürzende) Aussage, "Java-Compiler unterstützen keine Endrekursion" hatte mich nur irritiert.

 

[musiKk]

Ja. Mit der VM-Sache verschwimmen die Grenzen zwischen Interpretierung und reinem Compilat ja etwas. Normal hängt das am Compiler. Aber wenn die Aussage aus oben angegebener Diskussion stimmt, dass es in der JVM keine Möglichkeit für einen einfachen Sprung gibt (also quasi ein jmp in Assembler), dann liegt es wohl doch an der Spezifikation vom Bytecode. Aber mit Bytecode habe ich mich noch nicht so sehr beschäftigt, auch wenn ich das auch mal machen wollte.

 

[tfa]

Also einen Byte-Code für goto gibt es schon. Es gibt ja auch unbedingte Sprünge in Java (break, continue).
Ich denke, dass die Endrekursionsauflösung eher in funktionalen Sprachen üblich ist als in imperativen. Rekursive Programmierung ist da ja sowieso essentiell. Von daher ist eine eingebaute Unterstützung dort eher zu finden als in Java.

 

[musiKk]

Das stimmt schon. Nur weiß ich nicht, was dafür spricht, Endrekursion nicht zu berücksichtigen. Wie gesagt, der GCC machts und somit dürfte es auch für jede Sprache gehen, für die es ein GCC-Frontend gibt. Mit C gehts jedenfalls. Wollte es eigentlich auch noch mit dem gcj ausprobieren, aber der zog gleich wieder Unmengen an Abhängigkeiten mit sich, da hab ichs erstmal gelassen. 😉

 

[Landei]

Scala hat eine einfache Form der End-Rekursion (eben soweit sich das mit der JVM realisieren lässt), also könnte das der Java-Compiler auch implementieren.