# Rekursion und StackOverflow



## Scamas (10. Apr 2008)

ich implementiere gerade einen rekursiven region growing algorithmus. allerdings wird bereits nach ~5000 offenen methoden aufrufen ein StackOverflowError geworfen. ich habe sowas früher schon mal mit c++ und visual studio gemacht... dort hatte man die möglichkeit einen größeren stack für die applikation zu verwenden. geht das in java auch? bzw. welche möglichkeiten habe ich, um dieses problem zu lösen?

debian linux / java 6 / eclipse


----------



## Marco13 (10. Apr 2008)

http://java.sun.com/j2se/1.3/docs/tooldocs/solaris/java.html#options

java -Xms*6m* TheProgram

Du solltest das ganze aber besser iterativ machen....


----------



## Scamas (10. Apr 2008)

kommt noch ^^ ... ich implementiere sowohl rekursion als auch iterativ und führe einige vergleiche durch

danke für die schnell antwort


----------



## Scamas (10. Apr 2008)

hmm... auf den ersten blick ganz toll, auf den zweiten hats aber nahezu nichts gebracht... nun sind immerhin schon ~6000 aufrufe nötig bis die exception fliegt... scheinbar ist rekursion im bereich bildverarbeitung mit java nicht optimal/unbrauchbar


----------



## maki (10. Apr 2008)

Rekursion ist Rekursion, egal um was es geht.

Das Rekursion zwar im Code viel aussagen kann ist bekannt, aber auch das die Stackframes begrenzt sind, auf jeder Plattform und Programmiersprache.

Das allseits bekannte Gegenmittel: Iteration anstatt Rekursion.
Läuft auch schneller


----------



## Marco13 (10. Apr 2008)

Ja, du kannst ja auch
java -Xms*600m* TheProgram 
machen, aber irgendwann wird's sinnlos - insbesondere, weil das so klingt, als ob der Speicherplatzbedarf nicht linear, sondern polynomial (oder sogar exponentiell?) ist....


----------



## Scamas (22. Apr 2008)

ich nochmal...

ich habe mittlerweise zwar einen iterativen algorithmus als alternative, jedoch kann ich mir absolut nicht vorstellen, das java bei rekursion derart versagt.

das java kommando -Xms6m bewirkt rein gar nichts in bezug auf eine mögliche rekursionstiefe. der kurzzeitige eindruck dies würde ewas bringen erwies sich recht schnell als falsch.

hab ich irgendwas elementares übersehen?

für weitere ideen bin ich dankbar...


----------



## maki (22. Apr 2008)

> jedoch kann ich mir absolut nicht vorstellen, das java bei rekursion derart versagt.


Natürlich kannst du dir das nicht vorstellen, ist ja auch absoluter quatsch, dachte ich hätte das schon erklärt...

Schau doch mal hier rein: http://www.java-forum.org/de/viewtopic.php?t=67967&highlight=xss


----------



## SlaterB (22. Apr 2008)

warum tust du das so als Quatsch ab, hast du das schon getestet?
also ich kann diese Optionen auch nicht wirklich nachvollziehen,

java -Xss999 läuft bei mir nicht,
java -Xss1000 bis zu 262M läuft, hat aber anscheinend keine Auswirkung auf den Stack,
mit anderen Parametern verschieben sich die Grenzen etwas (z.B. kann ich nachvollziehen, dass bei 
-Xmx1024m Xss nur bis 110m geht, wie im anderen Thread angegeben), 
ein Sinn oder wenigstens eine Auswirkung ist aber nicht zu erkennen,

mein Programm läuft immer bis x= 5128


```
public class Test
{

    public static void main(String[] args)
        throws Exception
    {
        try
        {
            doSomething(0);
        }
        catch (Throwable t)
        {
            // sonst Spam der Fehlermeldung
        }
    }

    static void doSomething(int x)
    {
        System.out.println("x: " + x);
        doSomething(x + 1);
    }
}
```


----------



## maki (23. Apr 2008)

Quatsch deswegen, weil die Aussage das "Java keine Rekursion kann" imho nix anderes ist 

Nach ein bisschen Nachforschen kam heraus, das Java unter Windows einen "Bug" hat, der dafür sorgt, dass der Xss Parameter nur bei neuen Threads zieht.

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4689767

So geht's auch unter Windows:

```
package test;

public class RekursionsTest implements Runnable{


	public static void main(String[] args)
	throws Exception
	{
		try
		{    	  
			(new Thread(new RekursionsTest())).start();
		}
		catch (Throwable t)
		{
			System.out.println(t);
		}
	}


	void doSomething(int x)
	{
		System.out.println("x: " + x);
		doSomething(x + 1);
	}

	public void run() {
		doSomething(0);
	}

}
```
Hab ich bei ca. 1.5 Millionen manuell abgebrochen, da es funzt.


----------



## SlaterB (23. Apr 2008)

ah, sehr interessante Info, danke


----------



## maki (23. Apr 2008)

Muss zugeben, dass ich mich auch sehr gewundert habe, aber erst als ich es ausprobiert habe... (schäm)


----------

