recursion - 为什么递归导致的stackoverflow无法解决？

Question

任何递归都可以修改为具有堆栈结构的迭代函数，那我为什么要这样做呢？如果答案是避免stackoverflow，那么计算机怎么会通过递归来溢出呢？为什么编译器不默认或使用附加关键字自动将递归函数放在堆中的堆栈上？我知道堆也是有限的，但它比分配给程序的堆栈大得多。

Answer 1

根据C/C++ 程序的最大堆栈大小和MSDN，Windows 上的最大堆栈大小为 1 MiB。你的问题很有趣。关键字当然是可能的，编译器可以做到。您需要询问编译器制造商，但我想这不是一个非常有趣的功能。

由于堆栈上的其他局部变量和堆上的递归簿记变量，缓存会很困难。信息分散在记忆中。

一些递归算法可以变成真正的迭代算法（例如Factorial的计算），甚至可以变成封闭形式的表达式（例如，参见Fibonacci numbers）。这样，就不需要对递归调用进行簿记了。

Answer 2

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

有可能您可以比编译器使用非常通用的过程机制更有效地执行此操作（其效率可能会受到各种 ABI 问题的阻碍）。

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

Answer 3

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

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