# StackOverflow



## Shimona di Blasi (19. Apr 2008)

```
public class orginal {
	static int betrag[] = { 1, 2, 5, 10, 20, 50, 100, 200 };
	// Muenz-Nummern : 0 1 2 3 4 5 6 7
	static long Tab[][];

	public static long w(int G, int i) { // auf wieviele Arten kann
	// man den Betrag G mit Muenzen bis zur Nummer <= i herausgeben ?
		return (G < 0) ? 0 : (i == 0) ? 1 : (Tab[G][ i] != 0) ? Tab[G][ i]
				: (Tab[G][ i] = w(G, i - 1) + w(G - betrag[ i], i));
	}

	public static void main(String[] args) {
		int G = Integer.parseInt(args[0]);
		Tab = new long[G + 1][8];
		System.out.println("Orginal:Den Betrag von " + G + " kann man auf " + w(G, 7)
				+ " verschiedene Arten herausgeben.");
	}
}
```

folgendes nicht all zu großes Programm habe ich. Es berechnet die Anzahl der Möglichkeiten Wechselgeld zurückzugeben.

Wenn ich es allerdings mit großen Zahlen starte, bekomme ich einen StackOverflow.


Ich weiss jetzt nicht genau .. kommt der StackOverflow dadurch, dass der ArrayIndex zu groß wird, oder kommt er daher, dass der Wertebereich long überschritten wird?

Zweiterem könnte man ja mit BigInteger entgegenwirken, da bin ich auch gerade dran. Ich versuche nur jetzt auch noch eine Alternative zu dem zweidimensionalen Array zu finden. Ein Ansatz währe mit einer HashMap. Nur ist eine HashMap leider nur eindimensional. 
Darauf hin dachte ich, dass ich ein Array aus HashMaps machen kann, doch leider weiß ich nicht wie die Syntax dafür sein soll. Habe schon so gut wie alle Möglichkeiten dies zu erstellen versucht  .


----------



## Wildcard (19. Apr 2008)

Bei jedem Methodenaufruf wird die Rücksprungadresse und die Zustände der lokalen Variablen auf den Stack gepackt. Geht die Rekursion zu tief, läuft der Stack voll, was in besagter Exception endet.
Du hast 3 Möglichkeiten:
1. weniger tiefe Rekursion
2. mehr Stack
3. Rekursion durch eine iterative Lösung ersetzen


----------



## Gast (19. Apr 2008)

Hallo, danke!
Eine weniger tiefe Rekursion ist nicht so ohne weiteres Möglich.
Wie kann ich denn mehr Stack verwirklichen?


----------



## Wildcard (19. Apr 2008)

Mit dem -Xss Parameter (bei einer SUN VM).


----------



## Gast (20. Apr 2008)

Wo kann ich denn diesen Parameter angeben?


----------



## Beni (20. Apr 2008)

Auf der Kommandozeile. Wenn du da normalerweise "java deinProgramm" eintippst, dann gibst du jetzt "java -Xss1000 deinProgramm" ein, um den Stack auf eine Grösse von 1000 zu setzen (was ist eigendlich der default-Wert?)


----------



## Gast (20. Apr 2008)

ah habs gefunden. Welche größe empfehlt ihr mir?


----------



## Wildcard (20. Apr 2008)

Gast hat gesagt.:
			
		

> ah habs gefunden. Welche größe empfehlt ihr mir?


Eine mit der du für den von dir gewählten Maximalwert X keine StackOverflowException bekommst.


----------



## Gast (20. Apr 2008)

-Xss110m -Xmx1024m

damit läuft es recht gut, außer beim größten Wert den ich berechnen muss. 
Wenn ich Xss noch größer mache, startet das ganze gar nicht mehr. Gibt es noch irgendwo Variablen die ich dafür ändern kann?

Habe hier nur einen Laptop (dual Centrino, win xp, 1gb ram), könnte es zuhause nochmal auf meinem Desktop (athlon 64 3500+, 2gb ram, gentoo 64) ausprobieren. Glaubt ihr, dass die Größen da anders sind?


----------



## Marco13 (20. Apr 2008)

Ja, nimm halt -Xss1100m, oder mach' es iterativ. Ist ja nicht schwer, das umzuschreiben, wenn man weiß, was das Programm macht. (D.h. wenn man die Aufgabe bekommen hat, so eine Programm zu schreiben, und man es mit Beträgen von z.B. 10, 1000 und 100000 Euro testen soll, und man eben NICHT einfach die erstbeste Version des Programmes verwendet, das man mit einer passenden Websuche http://www.google.com/search?q="man+den+Betrag+G+mit+Muenzen"&hl=en&filter=0 gefunden hat, um sich mit fremden Federn zu schmücken und die Arbeit, die man sich für seinen Schein machen muss, zu minimieren. (Hoffetnlich sind die ganzen Tutoren und so clever genug, solche Betrugsversuche zu erkennen ....))


----------



## Gast (20. Apr 2008)

Danke für deinen Beitrag. Du hast genau das Programm gefunden, dass uns vorgegeben war. Die Aufgabenstellung war lediglich einige Werte zu berechnen, nicht das Programm zu schreiben.

Aber in diese Richtung sollte die Diskussion jetzt eigentlich nicht gehen 

Mit -Xss1100 geht es ja auch nicht wenn es nicht mal mit 128 geht


----------

