Segmentierungsfehler (core dumped) Fehler C++ rekursive Aufrufe

Question

Ich habe einen zyklischen Graphen von 4 Vertices.

Jeder Knoten ist mit einer Kante verbunden, die ich in einer Karte namens Nodelabel gespeichert habe.

Ich versuche printAll (Int-Quelle, Int-Tiefe) aufzurufen, die mir Pfad der Länge Tiefe von Quellknoten (Offset 0 bis Knotengröße) geben wird.

Wenn die Tiefe bis 650 ist, läuft es gut. In dem Moment, in dem ich printAll (2, 800) gebe, gibt es einen Segmentierungsfehler.

Ich habe debugged, dass der Fehler von printAllPathsUtil Funktion kommt ... Kann jemand mich auf den Grund hinweisen, warum Segmentierung Fehler passiert. ?

Graph g(4); // 4 nodes 
g.addEdge(0, 1); 
g.addEdge(0, 2); 
g.addEdge(2, 0); 
g.addEdge(2, 3); 
g.addEdge(3, 3); 

g.addLabel(0, "AAGT"); 
g.addLabel(1, "CCTC"); 
g.addLabel(2, "TTCC"); 
g.addLabel(3, "CTC"); 
map < int, string > nodelabel; // Map containing Nodelabel corresponding to every node id 
void Graph::addLabel(int v, string s) { 
    nodelabel[v] = s; // Add w to v’s list. 
} 

void Graph::printAllPaths(int source, int depth) { 
    string kmerpath; 
    int * path = new int[V]; 
    int path_index = 0; // Initialize path[] as empty 

    // Call the recursive helper function to print all paths 
    for (int offset = 0; offset < nodelabel[source].length(); offset++) { 
    printAllPathsUtil(source, offset, depth, path, path_index, kmerpath, 1); 
    path_index = 0; 

    } 
} 

void Graph::printAllPathsUtil(int u, int offset, int d, int path[], int & path_index, string kmerpath) { 
    path[path_index] = u; // store Current node in the path[] 
    path_index++; 

    if (d == 0) { 
    //cout << kmerpath << endl; 
    } else if ((nodelabel[u].length() - offset) >= d) { 
    kmerpath.append(nodelabel[u].substr(offset, d)); 
    printAllPathsUtil(u, offset, 0, path, path_index, kmerpath); 
    } else // If current vertex is not destination 
    { 
    // Recur for all the vertices adjacent to current vertex 
    list <int> ::iterator i; 
    kmerpath.append(nodelabel[u].substr(offset, (nodelabel[u].length() - offset))); 
    for (i = adj[u].begin(); i != adj[u].end(); ++i) { 
     printAllPathsUtil(* i, 0, (d - (nodelabel[u].length() - offset)), path, path_index, kmerpath); 
    } 
    } 
    path_index--; // Remove current vertex from path[] 

} 

Answer 1

Manchmal ist es nicht immer klar, wenn Sie Rekursion versus Schleifen verwenden. Rekursion wird oft als komplizierter angesehen und wird häufig mit einer funktionalen Programmierung verbunden, die sehr threadsicher sein soll. Sie können jedoch schnell aus dem Stapelspeicher gehen, wenn Sie zu tief in die Rekursion gehen.

Angenommen, Sie haben eine einfache Funktion:

char* foo() 
{ 
    char a[100000]; 
    memset(a, 0, 100000); 
    return a; 
} 

Das Programm weiß, wie viel Speicher, um es zu verteilen, wenn es (100.000 Bytes, plus ein wenig für die Anweisungen) aufgerufen wird.

char bar() 
{ 
    char* c = foo(); 
    char b = 1; 
    return c[0] + b; 
} 

wenn Sie foo() von woanders anrufen, dann geht das Programm kennt den Speicher für foo()-bar() plus ein wenig für bar() zuzuordnen.

char bar() 
{ 
    if (condition) 
    { 
    return foo() + bar(); 
    } 
    else return 0; 
} 

Aber wenn Sie bar() rekursiv zu machen, dann wird das Programm nicht wirklich wissen, wie viel zu reservieren, da sie keine Vorstellung davon hat, wie oft tief es geht. Es macht eine vernünftige Schätzung, aber wenn Sie die Tiefe überschreiten, die von der Schätzung unterstützt wurde, dann erhalten Sie einen Stapelüberlauf.

Die Lösung ist stattdessen Schleife, wenn excessibly tief gehen:

char bar() 
{ 
    char* a; 
    while (condition) 
    { 
    a += foo(); 
    } 
    return a; 
} 

In diesem Fall haben wir den functional Aspekt unseres Design zu verlieren, aber wir foo() nur einmal zu einer Zeit anrufen und so wird der Speicher wieder freigegeben Jedes Mal, wenn wir die Schleife zurücksetzen.

Ich hoffe, dass Erklärung war hilfreich und richtig sind. Ich weiß, dass die Funktionen nicht viel Sinn gemacht haben, aber hoffentlich gibt dir das die Idee.