# StackOverflowError bei Rekursion verhindern



## Schandro (14. Dez 2008)

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 (14. Dez 2008)

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 (14. Dez 2008)

Schandro hat gesagt.:
			
		

> 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 (14. Dez 2008)

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 (14. Dez 2008)

Schandro hat gesagt.:
			
		

> 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 (14. Dez 2008)

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 (15. Dez 2008)

musiKk hat gesagt.:
			
		

> > 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 (15. Dez 2008)

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


----------



## tfa (15. Dez 2008)

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


----------



## musiKk (15. Dez 2008)

tfa hat gesagt.:
			
		

> 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.



			
				tfa hat gesagt.:
			
		

> 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 (15. Dez 2008)

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


----------



## musiKk (15. Dez 2008)

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 (15. Dez 2008)

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 (15. Dez 2008)

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 (15. Dez 2008)

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.


----------

