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

Question

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

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

Answer 1

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

还可以使用连续传递样式(CPS)将其转换为尾递归形式。要做一个经典的例子，请考虑fibonacci函数。这可以用以下方式用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抽象。

动态结构(列表、堆栈、函数等)的使用在以前的所有例子中，都是必不可少的。也就是说，为了迭代地模拟泛型递归函数，您不能避免动态内存分配，因此通常无法避免堆栈溢出。

因此，内存消耗不仅与程序的迭代/递归性质有关。另一方面，如果阻止动态内存分配，程序本质上是有限状态机，计算能力有限(更有趣的是根据输入的维数来参数化内存)。

通常，正如无法预测终止一样，您也无法预测程序的未绑定内存消耗:使用图灵完整语言，在编译时不能避免发散，也不能避免堆栈溢出。

Answer 2

尾呼叫优化：

进行参数和调用的自然方法是在退出或返回时整理清理。

要使尾调用工作，您需要修改它，以便尾调用继承当前框架。因此，它没有创建新的框架，而是对框架进行按摩，以便下一个调用返回到当前函数调用者，而不是这个函数，这个函数实际上只在尾部调用时才会清理和返回。

因此，TCO主要是在最后一次调用之前进行清理。

延续传递风格-让尾巴呼喊出一切

编译器可以更改代码，使其只执行基本操作并将其传递给延续。因此，堆栈使用被移到堆上，因为要继续的计算是一个函数。

一个例子是：

function hypotenuse(k1, k2) {
  return sqrt(add(square(k1), square(k2)))
}

变成了

function hypotenuse(k, k1, k2) {
  (function (sk1) {
    (function (sk2) {
      (function (ar) {
         k(sqrt(ar));
      }(add(sk1,sk2));
    }(square(k2));
  }(square(k1));
}

注意，现在每个函数都有一个调用，并设置了计算顺序。

Answer 3

根据这个问题，所有的迭代循环都可以转化为递归。

“翻译”可能有点夸张。如果您理解图灵完备性，那么对于每个迭代循环都有等效递归程序的证明是微不足道的:因为图灵机可以使用严格的迭代结构和严格的递归结构来实现，所以可以用迭代语言表示的每个程序都可以用递归语言表示，反之亦然。这意味着对于每个迭代循环，都是，这是一个等价的递归构造(反过来也是如此)。然而，这并不意味着我们有一些自动的方式将其中一个转换成另一个。

这些迭代循环可以转化为尾递归。

尾递归可以很容易地转换成一个迭代循环，反过来也可以。但并不是所有的递归都是尾递归。下面是一个例子。假设我们有二叉树。它由node组成，每个node都可以有一个left、一个right子级和一个value。如果一个节点没有子节点，那么isLeaf为它返回true。我们假设有一些函数max返回两个值的最大值，如果其中一个值是null，则返回另一个值。现在，我们想要定义一个函数，它在所有叶节点中找到最大值。这是我做的一些伪代码。

findmax(node) {
    if (node == null) {
        return null
    }
    if (node.isLeaf) {
        return node.value
    } else {
        return max(findmax(node.left), findmax(node.right))
    }
}

max函数中有两个递归调用，因此不能对尾递归进行优化。我们需要两者的结果，然后才能将它们提供给max函数并确定对当前节点的调用结果。

现在，可能有一种方法可以获得相同的结果，使用递归和只使用一个尾递归调用。它在功能上是等价的，但它是一个不同的算法。编译器可以进行大量的转换来创建一个功能等价的程序，并进行大量的优化，但它们还不够聪明，无法创建功能等价的算法。

即使将只递归调用一次的函数转换为尾递归版本也远不是那么简单。这样的调整通常使用一些传递到递归调用中的参数，作为当前结果的“累加器”。

查看下一个用于计算一个数字的阶乘的简单实现(例如，事实(5)= 5*4*3*2*1)：

fact(number) {
    if (number == 1) {
        return 1
    } else {
        return number * fact(number - 1)
    }
}

不是尾递归的。但这样做是可以做到的：

fact(number, acc) {
    if (number == 1) {
        return acc
    } else {
        return fact(number - 1, number * acc)
    }
}
// Helper function
fact(number) {
    return fact(number, 1)
}

这需要对正在进行的工作作出解释。认识到像这样的事情是很容易的，但是如果你调用一个函数而不是一个乘法呢？编译器如何知道对于初始调用，累加器必须是1而不是0？你怎么翻译这个程序？

recsub(number) {
    if (number == 1) {
        return 1
    } else {
        return number - recsub(number - 1)
    }
}

到目前为止，这还超出了我们现在所拥有的编译器的范围，而且实际上可能一直如此。

也许在computer science Stack Exchange上问这个问题会很有趣，看看他们是否知道一些更深入研究这一问题的论文或证据。