我有一个递归函数，它在给定某些输入的情况下多次调用自己——这正是它应该做的。我知道我的函数不是无限循环的——它只是得到一定数量的调用和溢出。我想知道这是否是在堆栈上放置太多内存的问题，或者只是调用次数的正常限制。显然，很难说出最大的特定呼叫次数，但是任何人都可以给我一个数量级的粗略估计吗？数以千计吗？数百？百万？
问问题
806 次
5 回答
3
所以，正如你猜到的，问题是（同名的）堆栈溢出。每次调用都需要建立一个新的栈帧，将新的信息压入栈中；堆栈大小是固定的，最终会用完。
什么设置堆栈大小？这是编译器的一个属性——也就是说，它对于二进制可执行文件是固定的。在 Microsoft 的编译器（用于 VS2010）中，它默认为 1 兆字节，您可以在编译器选项中使用“/F”覆盖它（参见此处的 '03 示例，但语法相同）。
在实践中很难计算出多少次调用。函数的堆栈大小取决于它的局部变量、返回地址的大小以及参数的传递方式（有些可能会在堆栈上），而且很大程度上取决于架构。一般来说，您可能会假设后两个小于一百字节（这是一个粗略的估计）。前者取决于你在函数中做什么。如果您假设该函数在堆栈上占用 256 个字节，那么使用 1M 堆栈在溢出之前您将获得 4096 个函数调用——但这并没有考虑到主函数的开销等。
您可以尝试减少局部变量和参数开销，但真正的解决方案是Tail Call Optimization，其中编译器在调用递归函数时释放调用函数。您可以在此处阅读有关在 MSVC 中执行此操作的更多信息。如果您不能进行尾调用，并且您不能以可接受的方式减小堆栈大小，那么您可以使用“/F”参数查看增加堆栈大小，或者（首选解决方案）查看重新设计。
于 2012-04-13T18:21:57.627 回答
2
这完全取决于您在堆栈上使用了多少信息。但是，Windows 上的默认堆栈是 1MB，而 Unix 上的默认堆栈是 8MB。简单地进行调用可能涉及推送一些 32 位寄存器和返回地址，例如，因此您可能会查看 20 字节的调用，这将使 Windows 上的最大值约为 50k，Unix 上的最大值为 400k——对于一个空函数。
当然，据我所知，您可以更改堆栈大小。
于 2012-04-13T18:21:26.453 回答
0
您的一种选择可能是更改/增加默认堆栈大小。这是一种方法http://msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.80).aspx
于 2012-04-13T18:11:05.220 回答
0
有一些工具可以测量堆栈使用情况。他们预先用特定的字节模式填充堆栈，然后查看它改变的地址。通过这些，您可以了解您获得的极限有多接近。
也许其中一种 valgrind 工具可以做到这一点。
于 2012-04-13T18:45:52.713 回答
0
递归函数使用的堆栈空间量取决于递归的深度和每次调用使用的内存空间量。
递归的深度是指在任何给定时刻激活的调用级别数。例如，一棵二叉树可能有 100 万个节点，但如果它平衡良好，您可以在不超过 20 个同时活动调用的情况下遍历它。如果平衡不好，最大深度可能会大得多。
每次调用使用的内存量取决于递归函数中声明的变量的总大小。
递归的最大深度没有固定限制；如果您的总使用量超过系统施加的堆栈限制，您将获得堆栈溢出。
您可以通过以某种方式减少递归深度来减少内存使用量，也许可以通过重组您正在遍历的任何内容（您没有告诉我们太多），或者通过减少声明的任何本地对象的总大小在您的递归函数内部（请注意，堆分配的对象不会影响堆栈大小），或两者的某种组合。
正如其他人所说，您也许可以增加允许的堆栈大小，但这可能只会有有限的用途——这是您在运行程序之前必须做的额外事情。它还可能消耗资源并干扰系统上的其他进程（施加限制是有原因的）。
更改算法以避免递归可能是一种可能性，但同样，我们没有足够的信息来说明这一点。
于 2012-04-13T19:32:02.187 回答