如何避免递归函数的堆栈溢出？

Question

例如,如果我们通过跟随函数遍历一个相当大的树,我们可能会得到堆栈溢出.

void inorder(node* n)
{
  if(n == null) return;
  inorder(n->l);
  n->print();
  inorder(n->r); 
}

如何在函数中添加条件或某些东西以防止这种溢出发生？

Answer 1

考虑迭代而不是递归,如果这真的是一个问题.

http://en.wikipedia.org/wiki/Tree_traversal

请参阅psedo代码以进行迭代迭代迭代迭代预测迭代序列

基本上在while循环中使用自己的列表作为堆栈数据结构,可以有效地替换函数递归.

Answer 2

除了用堆栈的显式管理（使用 ）替换递归之外，没有可移植的解决方案 std::vector<Node*>。不可移植的是，您可以使用静态变量来跟踪深度；如果您知道最大堆栈大小以及每次递归需要多少堆栈，那么您可以检查深度是否超过该值。

许多系统（例如 Linux 和 Solaris）您无法预先知道最大堆栈深度，因为堆栈是动态分配的。然而，至少在 Linux 和 Solaris 下，一旦内存被分配给堆栈，它将保持分配状态并继续受到堆栈的影响。因此，您可以在程序开始时相当深入地递归（可能会崩溃，但在执行任何操作之前），然后稍后检查该值：

static char const* lowerBound = nullptr;

//  At start-up...
void
preallocateStack( int currentCount ) {
{
    char dummyToTakeSpace[1000];
    -- currentCount;
    if ( currentCount <= 0 ) {
        lowerBound = dummyToTakeSpace;
    } else {
        preallocateStack( currentCount - 1 );
    }
}

void
checkStack()
{
    char dummyForAddress;
    if ( &dummyForAddress < lowerBound ) {
        throw std::bad_alloc();   //  Or something more specific.
    }
}

您会注意到，该代码中存在一些未定义/未指定行为的情况，但我已经成功使用过几次（在 Sparc 上的 Solaris 下，但 PC 上的 Linux 在此情况下工作得完全相同）看待）。事实上，它几乎可以在任何系统上工作，其中： - 堆栈向下增长，并且 - 局部变量在堆栈上分配。因此，它也适用于 Windows，但如果它无法分配初始堆栈，则必须重新链接，而不是仅在盒子上的活动较少（或更改）时运行程序ulimits（因为堆栈Windows 上的大小在链接时是固定的）。

编辑：

关于使用显式堆栈的一条评论：某些系统（默认情况下包括 Linux）过度使用，这意味着在扩展 ; 时无法可靠地获得内存不足错误std::vector<>。系统会告知 std::vector<>该内存在那里，然后在程序尝试访问该内存时给予该程序一个段违规。