Rekusrion mit Stackoverflow

[nico3000]

Hi, ich hoffe, hier gibt's einige Experten, die mir weiterhelfen können.
Und zwar hab ich das Problem, dass immer wenn ich eine etwas größere rekursive Schleife programmiere, ich einen Stackoverflow bekomme.

Also, folgendes Problem:
Ich versuche das Springerproblem zu programmieren. Dafür hab ich ein schachBrett angelegt, deren Inhalt aus einzelnen schachFeld ern besteht. Jedes schachFeld hat ein array, welches auf von ihm erreichbare Felder verweist. Jetzt möchte ich zählen, wie viele Felder insgesamt von einem bestimmten Feld und all den benachbarten Feldern und deren Feldern usw. erreichbar sind. Idee: Ich hab eine Klasse programmiert, die einfach nur einen counter inkrementieren kann. Jetzt habe ich eine rekursive Abfrage programmiert:

public void calcTrace(zaehler z) {
  z.inc();
  traced = true;
  for(int i = 0; i < neighbours.length; i++) if(!neighbours[i].traced && neighbours[i].active) neighbours[i].calcTrace(z);
}

In traced wird gespeichert, ob dieses Feld schon gezählt wurde. DAmit man keine Endlosschleife bekommt und in active wird gespeichert, ob das Feld überhaupt noch aktiv ist, das heißt, noch mitgezählt werden soll. Für kleine Felder fuktioniert das alles perfekt, aber bei größeren gibt's einen Stacküberlauf.
Muss ich das jetzt iterativ lösen? Ich hab mir mal sagen lassen, alles, was iterativ gelöste werden kann, geht auch rekursiv.
Genau das gleiche Problem hab ich auch wenn ich andere Probleme durch Backracking rekursiv löse. Ich mein, dass mein Uni-Prof mal gesagt hat, Java wäre so intelligent und schmeißt bei Rekursionen bereits beendete Instanzen, in denen nichts mehr passiert (aber die trotzdem zum Schluss einen neue Instanz starten) aus dem Speicher. Hier aber anscheinend nicht.

Mach ich hier grundsätzlich etwas falsch?
Ich würde dem Programm nur ungern mehr Speicher zuweisen wollen, weil dann alle, die das Programm ausführen wollen, auch den Speicher zur Verfügung stellen müssten.
Weiß jemand Rat?

Nico

 

[SlaterB]

was hast du denn für ein Schachbrett, tausende Felder?

ich persönlich würde jede Rekursion über paar hundert vermeiden,
egal wie hoch nun genau die Grenze ist oder ob Java das optimiert,

bei deiner Operation ist das ja auch möglich:
Liste nichtbesuchter Felder führen (evtl. Map Feld -> Wert),
Schleife bis Liste leer: ein Feld rausnehmen, Nachbarn prüfen und vielleicht in Liste einfügen & Feld bearbeiten

 

[nico3000]

Naja, den Overflow gibts schon bei nem 80x80 Feld. Ich hatte die Listenlösung auch schon vorher, nur hab mir gedacht, ich brauch ja nur die Anzahl, dann muss ich ja nicht unbedingt noch eine Liste erstellen. Aber ich werd sie dann noch mal implementieren.
Aber wenn man solche großen Rekursionen vermeiden soll, dass kann man ja prinzipiell Backtracking nur für triviale Probleme rekursiv programmieren, oder? Dann würde die Regel, man könne alle iterativen Dinge auch rekursiv lösen ja falsch, oder sehe ich das falsch?

 

[Yzebär]

Wo setzt du denn das Flag "traced"?

Edit: Sieht aus, als wäre es eine Membervariable... vielleicht solltest du die gesamte Klasse posten.
Speziell das neighbours-Array ist interessant.

 

[SlaterB]

nicht so viel vermuten, erstmal testen,
gib der Operation calcTrace() einen int-Variable für die Tiefe mit
und gib die Tiefe jeweils aus
(um nicht zu viel auszugeben merke dir statisch die höchste bishergie Tiefe)

meist liegt die Tiefe höher als man denkt, aber bei Endlosschleifen (Programmierfehlern) ist irgendwann nun mal Schluss

-----

@Yzebär
Zeile 4 von 7 Zeilen

 

[nico3000]

Also, die maximale Tiefe müsste n*m sein, bei n Zeilen und m Spalten. Das hat der Test auch bestätigt. Bei 71x71 Feldern tritt der Überlauf auf.
Das neighbours-array enthält alle Felder, die von dem aktuellen aus erreichbar sind. Für einen Springer ist das minimal 2 lang (Ecke) und maximal 8 (mitten im Feld) und ich führ ja nur trace aus, wenn das Feld überhaupt noch aktiv ist, weil mich die nachbarn eines nicht aktiven Feldes ja gar nicht interessieren.
Der Algorithmus ist bisher schon recht effektiv. Er basiert zwar immer noch auf Backtracking (iterativ :wink: ) aber für viele Felder findet er schon nach n*m Schleifen eine Lösung, was ja das mindeste ist. Für ein 30x30 Feld braucht er nur 974 Durchläufe (für 10x11 hat er auch nach 50 Millionen noch nichts gefunden :roll:, aber für 11x10 schon nach 246 ???:L )
Das Problem ist halt nur, dass das Durchzählen einen Überlauf gibt. Wenn ich die Listen wieder reinnehme, hätte ich entweder viele Informationen doppelt gespeichert, oder ich müsste das halbe Programm wieder umschreiben.

 

[SlaterB]

wenn du die Feld-Größe änderst hat das nix zu sagen,

du vermutest,
bei 71x71 ist die (maximale) Tiefe 4900 ok
und bei 80x80 wäre 6400 ein Problem,

vielleicht macht dein Algoritthmus aber ganz was anderes,
so dass bei 71x71 50.000 erreicht wird, was ok ist, und bei 80x80 100.000, was zum Fehler führt,
du also bei einer Korrektur des Algorithmusses (so dass bei 71x71 wirklich nur maximal Tiefe 4900 erreicht wird)
deutlich größere Felder bearbeiten könntest

---------

aber das nur allgemein, ich dachte jetzt irgendwie an 80 Felder insgesamt und Max-Tiefe 80,
Max-Tiefe 4900 ist schon ein beachtlicher Wert,

da du ja in die Breite suchst und nicht der Länge nach,
wird die im Algorithmus erreichte Tiefe aber doch bestimmt viel niedriger liegen?
dann wäre es wieder die Frage, wie hoch die Grenze nun tatsächlich ist
-> testen mit Parameter, nicht mit Änderung des Feldes

(falls es dich überhaupt interessiert)

 

[nico3000]

hi, nochmal. in der letzten vorlesung haben wir nochmal genau gelernt, was es mit rekusrion auf sich hat. und diese rekusrion, die ich gemacht habe ist eine "allgemeine rekursion" und da wird rein gar nix optimiert das ist die speicherlastigste rekursion, die man sich nur denken kann... naja, ich denke, ich werd mein programm als beendet ansehen. es würde sowieso viiiiel zu lange dauern, einen weg zu finden, wenn er nicht auf anhieb gefunden wurde.
danke für eure hilfe. klasse forum ist das. und ich denke, dass ich bestimmt wieder eure wertvolle zeit in anspruch nehmen muss