由于有限递归导致的段错误

Question

我收到一个段错误，我认为这是由大量递归调用引起的。这已被记录 here。我的困惑是递归不是无限的；一旦给定事件发生，就会有一个明确的转折点，并且该事件最终将始终发生。我怀疑问题是中断前的递归调用次数太多了。 valgrind 的输出：

==903368== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==903368==
==903368== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==903368==  Access not within mapped region at address 0x1FFE801FF8
==903368== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==903368==    at 0x4081B4: operator-(Point const&, Point const&) (Point.h:47)
==903368==  If you believe this happened as a result of a stack
==903368==  overflow in your program's main thread (unlikely but
==903368==  possible), you can try to increase the size of the
==903368==  main thread stack using the --main-stacksize= flag.
==903368==  The main thread stack size used in this run was 8388608.
==903368== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==903368==
==903368== Process terminating with default action of signal 11 (SIGSEGV)
==903368==  Access not within mapped region at address 0x1FFE801FE8
==903368== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==903368==    at 0x482F14D: _vgnU_freeres (vg_preloaded.c:57)
==903368==  If you believe this happened as a result of a stack
==903368==  overflow in your program's main thread (unlikely but
==903368==  possible), you can try to increase the size of the
==903368==  main thread stack using the --main-stacksize= flag.
==903368==  The main thread stack size used in this run was 8388608.
==903368==
==903368== HEAP SUMMARY:
==903368==     in use at exit: 86,717 bytes in 40 blocks
==903368==   total heap usage: 52,536 allocs, 52,496 frees, 47,716,014 bytes allocated
==903368==
==903368== LEAK SUMMARY:
==903368==    definitely lost: 0 bytes in 0 blocks
==903368==    indirectly lost: 0 bytes in 0 blocks
==903368==      possibly lost: 0 bytes in 0 blocks
==903368==    still reachable: 86,717 bytes in 40 blocks
==903368==         suppressed: 0 bytes in 0 blocks
==903368== Rerun with --leak-check=full to see details of leaked memory
==903368==
==903368== For lists of detected and suppressed errors, rerun with: -s
==903368== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

重现尝试：

void f(int i, const int& niter) {
    i++;
    if (i < niter)
        f(i, niter);
    else 
        return;
}

int main()
{
    // fine
    f(0, 1000);
    
    // not fine
    f(0, 1000000);
    return 0;
}

我应该按照 valgrind 的建议增加主堆栈大小吗？或者完全避免递归？

int main()
{
    int i = 0;
    while (i < 1000000) 
        i++;
}

Answer 1

每一级递归都会占用一定量的栈内存。在所有平台上，我都知道堆栈有一个固定的（但可配置的）相对较小的大小。

最终递归的次数限制为 (stack size) / (stack used per call)，因此要增加递归的次数，您需要增加堆栈的大小或减少每次调用所需的大小。在您的示例中，您似乎有一个 8mb 的堆栈，因此要实现 1,000,000 级递归，每个级别只能在堆栈上分配 8 个字节，这在大多数实现中可能是不可能的。

减小每次调用大小的一种方法是传递对包含任何静态参数而不是单个参数的结构的引用。在您的示例中，这无济于事，因为您只有一个静态参数。在 int 小于指针的平台（例如大多数 64 位平台）上可能有帮助的是删除 const& 因为引用很可能作为指针传递。

如果上述方法不起作用，那么递归应该可以用非递归实现替换，并将您的状态存储在堆分配的 std::stack 中，因此不会导致堆栈溢出。

Answer 2

您应该将函数更改为非递归的。在大多数现代架构（包括 x86）中，递归是在堆栈上实现的，堆栈是有限的：它相对较小，不会根据需要增长。因此，作为经验法则，您应该避免使用递归函数，因为它们存在堆栈不足的已知问题。

递归似乎是问题的完美匹配，但这正是您作为人类思考算法的方式。然而，每个递归函数都可以相对容易地转换为非递归函数，在动态结构中保持步态，如 std::stack。还有很多递归算法至少有一个已知的非递归等价算法。

所以我鼓励您将函数转换为非递归函数并完全避免递归函数（在学习练习之外）

Answer 3

正如其他人提到的那样，递归很昂贵，你应该采用迭代的方式。但是在你的情况下，如果你对数学有一点了解，你可以使你的问题非常非常有效....

简单地说，您可以像这样将最后一个值存储在变量中：

int last = 1000;

然后执行以下操作：

int total = (last + 1)*last /2;

所以你的算法复杂度为 O(1);

由于有限递归导致的段错误

segfault due to finite recursion

c++

recursion

valgrind