recursion - 在函数式语言中，编译器如何将非尾递归转换为循环以避免堆栈溢出(如果有的话)？

Question

我最近一直在学习函数式语言以及其中有多少不包含 for 循环。虽然我个人并不认为递归比 for 循环更难(而且通常更容易推理)，但我意识到许多递归示例不是尾递归，因此不能使用简单的尾递归优化来避免堆栈溢出。 According to this question ，所有迭代循环都可以转化为递归，而那些迭代循环可以转化为尾递归，所以当question like this上的答案让我感到困惑如果你想避免堆栈溢出，建议你必须自己显式管理递归到尾递归的转换。似乎编译器应该可以完成从递归到尾递归的所有转换，或者从递归直接到迭代循环的所有转换，而不会出现堆栈溢出。

函数式编译器是否能够在更一般的递归情况下避免堆栈溢出？您是否真的被迫自己转换递归代码以避免堆栈溢出？如果他们不能执行一般的递归堆栈安全编译，那他们为什么不呢？

Answer 1

任何递归函数都可以转换为尾递归函数。例如，考虑图灵机的转换函数，即是从一个配置到下一个配置的映射。模拟图灵机你只需要迭代转换函数直到你达到了最终状态，这很容易用尾递归表示形式。同样，编译器通常将递归程序翻译成一个迭代的，只是添加一堆激活记录。

你也可以使用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)内存消耗:使用编译时的图灵完备语言你无法避免分歧，你也无法避免堆栈溢出。