Ich bekomme eine Stackoverflow Exception in meinem Algorithmus. Der durchläuft ein Netzwerk/Graphen rekursiv, um eine Liste aller Knoten zu erstellen (Tiefensuche). Für Graphen mit sehr langen Pfaden erhalte ich aber eine stackoverflow Exception - soweit so logisch. Was kann ich denn machen, um die stackoverflow Exception zu vermeiden? Ich muss den ganzen Graphen durchsuchen und kann nicht irgendwo anhalten. Außerdem spinnt der Debugger manchmal, weil er einfach ausgeht wenn der Stackoverflow auftritt oder keine Variablen mehr anzeigen kann usw.

Ich programmiere in C#.

Der rekursive Algorithmus kann umgeschrieben werden und zwar derart dass mit Stack<T> gearbeitet wird. Das Grundprinzip ändert sich nicht.

Also den Stack aufbauen und dann abarbeiten.

Bei mir werden die Knoten eines Graphen meist in einer separaten Liste des Graphen abgelegt. So braucht sich ein einzelner Knoten nur um die Verknuepfung zu anderen kuemmern. Waehrend geeignete add- und remove-Methoden der Graphklassen, Knoten hinzufuegen oder entfernen. Damit waere das Problem erledigt, alle Knoten zu finden.

Um eine Rekursion aufzulösen musst Du sie in eine iterative Variante (also unter Verwendung einer Schleife mit Hilfe eines - wie bereits angesprochen - Stacks umschreiben. Um mehrere Stacks zu vermeiden kannst Du auch einen Stack verwenden, in dem Du Dir eine Klasse baust, welche die notwendigen Parameter kapselt.

Hier zwei stark vereinfachte Beispiele. Dies ist eine rekursive Funktion die sich selbst aufruft, die Punkte symbolisieren Deine Programmlogik.

void Rekursiv(parameter1) {
    //...
    if (bedingung)
        Rekursiv(p1);
    else
        return;
}

und nun Itertiv nur mit einer Schleife. Dort wird der Parameter den Du sonst an Deine Funktion übergibst anstelle eine Funktionsaufrufs auf den Stack gelegt . Dieser wird innerhalb der Schleife verarbeitet. Brauchst Du einen weiteren Aufruf/Durchlauf wird dieser (mit Push()) auf den Stack gelegt. Solange bis der Stack leer ist, dann hast Du alles durchgearbeitet. Pop() entfernt das oberste Element auf dem Stack. Je nach Programmlogik sieht das dann sicherlich etwas anders aus als im Beispiel.

void Iterativ() {
    Stack.Push(p1);

    while (Stack.Count > 0) {
        //...
        if (bedingung)
            Stack.Push(p1);
        else
            p1 = Stack.Pop();
        //...
    }
end function

Falls Du ein praktisches Beispiel benötigst kannst Du Dir ja mal den Quicksort Algorithmus ansehen. Den kann man rekursiv programmieren (was auch schnell einen Stackoverflow auslöst) aber eben auch iterativ. Im Netz findet man beide Varianten.