如何修复递归函数导致的堆栈溢出错误?C++

Question

正如标题所示，我认为递归函数导致我的程序堆栈溢出。并且需要递归逻辑，如何解决？

法典：

static bool orient_flip_face(HE *edge)
{
if(edge->flip == NULL)
return 1;
return orient_face(face);
}
static bool orient_face(HEF *face)
{
assert(face->oriented);
return orient_flip_face(face->edge);
}
static bool build_HE(he::Mesh_Data *mesh,
std::vector<HEV*> *hevs,
std::vector<HEF*> *hefs)
{
// process mesh data
// ...
return orient_face(first_face);
}

基本上orient_face和orient_flip_face来回调用对方，直到最后一个顶点。当我传递一个简单的网格时，这很好，但是当我通过具有 63690 个顶点的斯坦福兔子时，它溢出了。然后我将堆栈反转大小增加到40MB，它修复了堆栈溢出错误。但这是一个合理的解决方案吗？

谢谢！

Answer 1

您的代码是尾递归的一个示例，因为递归调用是每个函数中执行的最后一件事。尾递归很容易转换为非递归循环。以下代码等效于您拥有的代码，并且根本不使用递归。

static bool orient_face(HEF *face)
{
for (;;)
{
assert(face->oriented);
HE *edge = face->edge;
if (edge->flip == NULL)
return 1;
}
}
static bool build_HE(he::Mesh_Data *mesh,
std::vector<HEV*> *hevs,
std::vector<HEF*> *hefs)
{
// process mesh data
// ...
return orient_face(first_face);
}

正如一些程序员指出的那样，代码实际上是一个无操作(断言除外，但我假设这只是一个调试细节，而不是代码的重点(。因此，除非有其他事情发生，否则您可以完全删除它。

细节决定成败。

Answer 2

你可能会遇到巨大的递归甚至无限递归循环。尝试检查基本情况条件，并验证递归是否在有限限制内停止。