我最近一直在学习函数式语言以及其中有多少不包含 for 循环。虽然我个人并不认为递归比 for 循环更难(而且通常更容易推理)，但我意识到许多递归示例不是尾递归，因此不能使用简单的尾递归优化来避免堆栈溢出。 According to this question ，所有迭代循环都可以转化为递归，而那些迭代循环可以转化为尾递归，所以当question like this上的答案让我感到困惑如果你想避免堆栈溢出，建议你必须自己显式管理递归到尾递归的转换。似乎编译器应该可以完成从递归到尾递归的所有转换，或者从递归直接到迭代循环的所有转换，而不会出现堆栈溢出。
函数式编译器是否能够在更一般的递归情况下避免堆栈溢出？您是否真的被迫自己转换递归代码以避免堆栈溢出？如果他们不能执行一般的递归堆栈安全编译，那他们为什么不呢？
最佳答案
任何递归函数都可以转换为尾递归函数。 例如，考虑图灵机的转换函数，即 是从一个配置到下一个配置的映射。模拟 图灵机你只需要迭代转换函数直到 你达到了最终状态，这很容易用尾递归表示 形式。同样，编译器通常将递归程序翻译成 一个迭代的，只是添加一堆激活记录。
你也可以使用continuation 翻译成尾递归形式 传球风格(CPS)。举一个经典的例子，考虑斐波那契 功能。 这可以通过以下方式用 CPS 样式表示，其中第二个 参数是延续(本质上是一个回调函数):
def fibc(n, cont):
if n <= 1:
return cont(n)
return fibc(n - 1, lambda a: fibc(n - 2, lambda b: cont(a + b)))
同样，您正在使用动态数据结构模拟递归堆栈: 在这种情况下，lambda 抽象。
动态结构(列表、堆栈、函数等)在所有之前的应用中的使用 例子是必不可少的。也就是说，为了模拟一个泛型 递归函数迭代，你无法避免动态内存分配， 因此，一般来说，您无法避免堆栈溢出。
因此，内存消耗不仅与迭代/递归有关 程序的性质。另一方面，如果你阻止动态内存 分配，你的 程序本质上是有限状态机，具有有限的计算能力 功能(更有趣的是根据 输入的维度)。
一般来说，就像你无法预测终止一样，你也无法 预测程序的未绑定(bind)内存消耗:使用 编译时的图灵完备语言 你无法避免分歧，你也无法避免堆栈溢出。
关于recursion - 在函数式语言中，编译器如何将非尾递归转换为循环以避免堆栈溢出(如果有的话)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43784575/