Hallo,
ich schreibe gerade an einer Anwendung, die zur Erstellung von Irrgärten regen Gebrauch von Rekursion macht und damit entsprechend viel Speicher im Stack benötigt. Ab einer gewisseen Größe bzw. Zellenanzahl ist Schluss. Natürlich könnte ich eine Art Obergrenze festlegen, aber die müsste relativ niedrig liegen, um die StackOverflowException
zu vermeiden ...
Ist eine iterative Lösung wesentlich speichersparender als die rekursive?
Edit: Oder ist der Code im folgenden Post ungünstig in Hinblick auf Rekursion geschrieben?
m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
Hier noch ein Screenshot und der Code der rekursiven Methode (hoffe, er ist dennoch verständlich).
/// <summary>
/// Expands the way from a given cell.
/// </summary>
private void Expand(Cell currentCell)
{
if (_visitedCells >= TotalCells)
{
return;
}
Cell neighborCell = null;
int[] directions = RandomHelper.GetDirections();
bool connected = false;
for (int index = 0; index < directions.Length; index++)
{
neighborCell = GetNeighborCell(currentCell, directions[index]);
if (neighborCell != null && !neighborCell.Visited)
{
currentCell.Connect(neighborCell);
connected = true;
_visitedCells++;
_cellStack.Push(neighborCell);
break;
}
}
if (!connected)
{
neighborCell = _cellStack.Pop();
}
Expand(neighborCell);
}
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
Hallo JAck30lena,
genau, das war meine Überlegung, aber ist diese Lösung wesentlich speichersparender?
m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
Es gibt die Möglichkeit, mit dem Stack-Objekt aus dem Framework zu arbeiten: Logikproblem beim Füllen einer fläche
Christian
Weeks of programming can save you hours of planning
Hallo JAck30lena,
gut, dann schreibe ich halt eine iterative Variante. Danke!
Hallo MrSparkle,
ich verwende bereits Stack<Cell>
!
m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
ich verwende bereits
Stack<Cell>
!
Aber eben nicht so, wie ich meinte. Mein Vorschlag war ein Ersatz für den rekursiven Aufruf der Expand-Methode!
Weeks of programming can save you hours of planning
Hallo MrSparkle,
huhu, der 1000. Beitrag 😉.
Ah, jetzt verstehe ich ... Ich glaube, das mache ich ...
m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
Zu Testzwecken könntest du auch die StackSize hochschraubben. Thread Constructor (ThreadStart, Int32)
Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...
Hi m0rius,
Da deine Funktion sogar endrekursiv ist, kannst du es wirklich ganz einfach in eine Schleife umformen. Ohne irgendwelchen zusätzlichen Speicherplatz.
private void Expand(Cell currentCell)
{
while(true)
{
if (_visitedCells >= TotalCells)
{
return;
}
Cell neighborCell = null;
int[] directions = RandomHelper.GetDirections();
bool connected = false;
for (int index = 0; index < directions.Length; index++)
{
neighborCell = GetNeighborCell(currentCell, directions[index]);
if (neighborCell != null && !neighborCell.Visited)
{
currentCell.Connect(neighborCell);
connected = true;
_visitedCells++;
_cellStack.Push(neighborCell);
break;
}
}
if (!connected)
{
neighborCell = _cellStack.Pop();
}
//Expand(neighborCell);
currentCell = neighborCell;
}
}
natürlich kannst du dann den Code auch wieder vereinfachen:
private void Expand(Cell currentCell)
{
while(_visitedCells < TotalCells)
{
Cell neighborCell = null;
int[] directions = RandomHelper.GetDirections();
bool connected = false;
for (int index = 0; index < directions.Length; index++)
{
neighborCell = GetNeighborCell(currentCell, directions[index]);
if (neighborCell != null && !neighborCell.Visited)
{
currentCell.Connect(neighborCell);
connected = true;
_visitedCells++;
_cellStack.Push(neighborCell);
break;
}
}
currentCell = (connected) ? neighborCell : _cellStack.Pop();
}
}
beste Grüße
zommi
Hallo m0rius,
eine Rechtsrekursion ist doch total simpel in eine Schleife umzusetzen? Wo ist dein Problem?
herbivore
PS: Ein bisschen zu spät.
Hallo zommi,
bis auf die beiden Klammern in der drittletzten Zeile hast du gerade das gepostet, was ich im Programm stehen habe 😉.
Hallo herbivore,
das habe ich auch nie abgestritten!
Edit: Mein Problem war eher dieser Gedankenfehler:
um speicher geht es hierbei nicht. es geht um den stack und wenn du rekursion vermeidest, hast du auch keine probleme mit dem stack.
m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
Hallo nochmal,
jetzt könnt ihr sehen, wofür sich die Mühe gelohnt hat 😉 ...
YAMG - Yet Another Maze Generator
m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg