Rekursive Ackermann-Funktion erzeugt Stack-Overflow

Walli

Hallo zusammen,
ich habe in meiner Informatikübung in Java die Ackermannfunktion rekursiv implementiert und verschiedene Test gemacht. Bei ack(4, 1) kommt allerdings nach < 1s ein Stack-Overflow. Kann ich da irgendwelche Parameter mitgeben, damit er länger durchhält? Benutze das normale JDK 1.4.2 über die Kommandozeile.

Edit: Das hier ist der Code:

public static int ack(int x, int y) 
	{
		if(x == 0) return y + 1;
		else if(x > 0 && y == 0) return ack(x - 1, 1);
		else return ack(x - 1, ack(x, y - 1));
	}

Gruß,

Mastah

Bashar

clisp produziert ungefähr nach 2 min. einen Overflow, vielleicht ist das normal?

Walli

Ja, aber warum stellen die uns dann so ne blöde Aufgabe. Es hieß in etwa: "Prüfen sie, für welche x \in {1,2,3,4} und für welche y < 100 die Funktion in weniger als ~10 sec einen Wert liefert." Das tolle ist aber, dass für ack(1, 100) und ack(2,100) das Ding in Nullkommanix durchläuft. Aber bei ack(3,10) und ack(4,0) produziert das Ding nen Stack-Overflow. Mir ist klar, dass auch ein ungeheurer Rechen-/Speicheraufwand dahinter steckt wenn x größer wird, aber man muss doch der VM irgendwie sagen können "Hey VM, du hast jetzt einen Riesenstack"...

Habs so probiert:

java -ss50m -oss50m Ackermann

Das schien ihn aber völlig kalt zu lassen. Hat niemand eine Idee? *wein*

Bashar

OK also in C läuft das Ding hier in 2min durch, muss doch an Java liegen.

Walli

Hab grad meinen Tutor gefragt. Der meint es läuft unter Linux auch durch. Muss wohl an der Windows-Implementation der VM liegen...

Bashar

Naja, die Java-Version hat sich bei mir unter Linux nach 5 1/2 min verabschiedet...

Walli

Immerhin .