为什么由递归引起的stackoverflow无法解决？

问题描述：

任何递归都可以修改为堆栈结构的迭代函数，那么为什么我要这样做呢？如果答案是为了避免计算器溢出，那么计算机如何通过递归溢出？为什么编译器会自动默认或使用其他关键字将堆递归函数放入堆栈中？我理解堆也是有限的，但它比分配给程序的堆栈大得多。为什么由递归引起的stackoverflow无法解决？

堆不是无限要么... –

[尾递归函数（http://stackoverflow.com/questions/33923/what-is-tail-recursion/33928#33928）可被重新写为迭代函数，但许多递归函数不是尾递归的。 – Simon

每个进程都在32位计算机上获得4GB虚拟内存，其中2GB分配给操作系统数据结构。因此堆栈的大小受到限制并可能溢出。 –

答

激活记录确实可以分配堆，但通常认为这太昂贵。尽管有一些采用这种方法的实现：例如，Stackless Python和SML/NJ。

在这些情况下，动机可能是帮助执行延续，而不是“修复”堆栈溢出。

答

根据C/C++ maximum stack size of program和MSDN，Windows上的最大堆栈大小为1 MiB。你的问题很有趣。关键字肯定是可能的，编译器可以做到这一点。你需要问编译器制造商，但我想这不是一个非常有趣的功能。

由于堆栈上的其他局部变量以及堆上的递归簿记变量，缓存将很困难。信息分散在内存中。一些递归算法可以转化为真正的迭代算法（如计算Factorial），甚至可以转化为封闭形式的表达式（例如参见Fibonacci numbers）。然后，不需要记录递归调用。

DEFAULT最大堆栈为1（和VS！= windows） –

答

在迭代过程中，您可以自己跟踪递归状态。

如果编译器能够使用非常通用的过程机制（其效率可能受到各种ABI问题的阻碍），那么可以更高效地实现这一点。

堆栈检查是可能的，但在所有系统上并不容易，因为并非所有系统都使用固定堆栈或线性地址空间。它当然也有开销，因为检查被添加到每个递归中。