C++中递归调用的最大数量级的数量级是多少？
我有一个递归函数，它在给定某些输入时调用自己很多次 - 这正是它应该做的。我知道我的函数并不是无限循环的 - 它只会达到一定数量的调用和溢出。我想知道在堆栈中放置太多内存还是一个问题，或者只是一个正常的调用数量限制。很显然，很难说具体的最大呼叫次数，但任何人都可以粗略地估计一下数量级？它在成千上万吗？数百？百万？C++中递归调用的最大数量级的数量级是多少？
它完全取决于你在堆栈上使用多少信息。但是，Windows上的默认堆栈为1MB，而Unix上的默认堆栈为8MB。简单地打一个电话可能需要推送几个32位寄存器和一个返回地址，例如，你可能会看到一个电话可能有20bytes，这将使Windows的最大值约为50k，而Unix上的最大值为400k--这是一个空函数。
当然，据我所知，您可以更改堆栈大小。
（注意：你总是可以责怪奔腾部门的bug！） – 2012-04-13 18:23:23
Whoopsies™。 fixedski – Puppy 2012-04-13 18:25:36
所以，正如你所猜测的，问题是（同名）堆栈溢出。每次通话都需要设置一个新的堆栈帧，将新的信息推送到堆栈上;堆栈大小是固定的，并最终用完。
什么设置堆栈大小？这是编译器的一个属性 - 也就是说，它对二进制可执行文件是固定的。在微软的编译器中（在VS2010中使用）它默认为1兆字节，你可以在编译器选项中用“/ F”覆盖它（关于'03例子，请参见here，但语法相同）。
很难弄清楚在实际中有多少个呼叫等同。函数的堆栈大小取决于它的局部变量，返回地址的大小，以及参数如何传递（有些可能会在堆栈中），而且大部分依赖于体系结构。一般来说，你可能会认为后两者小于一百字节（这是一个总估计）。前者取决于你在功能上做了什么。如果您认为函数需要比如256个字节的堆栈，那么在1M堆栈中，您将在溢出之前获得4096个函数调用 - 但这并不考虑主函数的开销等。
您可以尝试减少局部变量和参数开销，但真正的解决方案是Tail Call Optimization，其中编译器在调用递归函数时释放调用函数。你可以阅读关于在MSVC here中做更多的事情。如果你不能调用tail函数，并且你不能减小你的堆栈大小，那么你可以用“/ F”参数来查看堆栈大小，或者（首选的解决方案）看一下重新设计。
有工具可以测量堆栈使用情况。他们预先用特定的字节模式填充堆栈，然后查看它改变的地址。通过这些，你可以发现你有多接近极限。
也许valgrind工具可以做到这一点。
递归函数使用的堆栈空间量取决于递归的深度和每个调用使用的内存空间量。
递归的深度指的是在任何给定时刻活动的级数。例如，二叉树可能有一百万个节点，但如果平衡良好，则可以不超过20个同时活动呼叫来遍历它。如果平衡不好，最大深度可能会更大。
每次调用使用的内存量取决于在递归函数中声明的变量的总大小。
递归的最大深度没有固定的限制;如果您的总使用量超过系统强加的堆栈限制，则会发生堆栈溢出。
您可以通过某种方式减少递归的深度，也许可以通过重构任何它正在遍历的内容（您没有多告诉我们这些内容），或者通过减少在递归函数中声明的任何本地对象（请注意，堆分配的对象不会影响堆栈大小），或者两者的某种组合。
正如其他人所说的，您可能会增加您允许的堆栈大小，但这可能只是有限的使用 - 而且这是在运行程序之前必须做的额外事情。它也可能消耗资源并干扰系统上的其他进程（由于某种原因限制）。
更改算法以避免递归可能是一种可能性，但我们再次没有足够的信息来说明这一点。
这取决于你在每次通话中有多少东西。 – Mysticial 2012-04-13 18:06:49
如果它溢出堆栈“正是它应该做的”，那么你应该改变一下算法。 – 2012-04-13 18:07:51
我感觉到了力量的一个扰动。如果你甚至接近这种限制，我会建议一个迭代解决方案:) – 2012-04-13 18:15:20