Segmentation Fault (core dumped ) error C++ recursive calls

Question

I have a cyclic graph of 4 vertices.

Each node is associated with a edge which I stored in a map called nodelabel.

I am trying to call printAll(int source, int depth) which will give me path of length depth from source node(Offset 0 to node size).

When depth is till 650 it is running fine. The moment I give printAll(2, 800) it is giving segmentation fault.

I have debugged that the error is coming from printAllPathsUtil function...Can anybody point me towards the reason why segmentation fault is happening. ?

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

Sometimes it isn't always clear when you use recursion versus looping. Recursion is often considered more complicated, and is frequently associated with functional programming, intended to be very thread safe. However, you can quickly run out of stack memory if you go too deep in the recursion.

Let's say you have a simple function:

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

The program knows how much memory to allocate to it when it gets called (100,000 bytes, plus a little for the instructions).

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

if you call foo() from somewhere else, then the program knows to allocate the memory for foo() to bar() plus a little for bar().

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

But if you make bar() recursive, then the program doesn't really know how much to allocate because it doesn't have any idea of how many times deep it will go. It makes a reasonable guess, but if you exceed the depth that was supported by the guess, then you'll get a stack overflow.

The solution is to loop instead when going excessibly deep:

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

In this case we lose the functional aspect of our design, but we only call foo() once at a time and so the memory is released again each time we reset the loop.

I hope that explanation was helpful and correct. I know that the functions didn't make much sense, but hopefully if gives you the idea.