分割错误(核心转储)错误C++递归调用
问题描述:
我有一个4个顶点的循环图。分割错误(核心转储)错误C++递归调用
每个节点都与我存储在名为节点标签的映射中的边相关联。
我想调用printAll(int source,int depth),它会给我从源节点(偏移量0到节点大小)的长度深度路径。
当深度达到650时,它运行良好。我给printAll(2,800)的那一刻就是分段错误。
我调试了错误来自printAllPathsUtil函数......任何人都可以指出我为什么出现分段错误的原因。 ?
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[]
}
答
有时,当您使用递归与循环时,并不总是很清楚。递归通常被认为更复杂,并且经常与函数式编程相关,旨在非常安全。但是,如果你在递归中太深入,你可能会很快耗尽堆栈内存。
比方说,你有一个简单的功能:
char* foo()
{
char a[100000];
memset(a, 0, 100000);
return a;
}
程序知道多少内存分配给它时,它被调用(100,000字节,再加上一点点的说明)。
char bar()
{
char* c = foo();
char b = 1;
return c[0] + b;
}
,如果你从别的地方调用foo()
,则程序知道分配内存为foo()
到bar()
再加上一点点的bar()
。
char bar()
{
if (condition)
{
return foo() + bar();
}
else return 0;
}
但是,如果你bar()
递归,然后该程序并不真正知道多少来分配,因为它不具备的怎么会深很多次去的想法。这是一个合理的猜测,但是如果超过了猜测所支持的深度,那么你会得到一个堆栈溢出。
解决方案是循环而不是去当excessibly深:
char bar()
{
char* a;
while (condition)
{
a += foo();
}
return a;
}
在这种情况下,我们失去了我们的设计functional
方面,但我们只在一个时间打电话foo()
一次,所以内存再次释放每次我们重置循环。
我希望这个解释有帮助和正确。我知道这些功能没有什么意义,但希望如果给你的想法。
你用C++编程,你写道你是。那你为什么把问题标记为C? C和C++不是相同的语言,不要混淆它们。 – Rakete1111
对不起。我认为有这方面知识的人也可以帮助我。 – rombi
@rombi _“任何人都可以指出我发生分段错误的原因吗?”_堆栈溢出?如果使用递归,那很可能。尝试用循环和'std :: stack'替换递归。 –