方案和调用堆栈中的递归

Question

我是一名大学生，学习球拍/方案和C作为我的CS学位的入门课程。

我在网上读到，在C语言中使用迭代而不是递归通常是最佳实践，因为递归由于将堆栈帧保存到调用堆栈上而代价高昂。。。

现在，在类似于Scheme的函数式语言中，递归一直在使用。我知道尾部递归在Scheme中是一个巨大的优势，据我所知，它只需要一个堆栈帧（有人能澄清这一点吗？）无论递归有多深。

我的问题是：非尾递归呢？每个函数应用程序是否保存在调用堆栈上？如果我能得到一个如何工作的简要概述，或给我一个资源，我将不胜感激；我似乎找不到一个明确说明这一点的地方。

Answer 1

是的，处于非尾部位置的调用需要向堆栈中添加一些内容，以便它知道如何在调用返回时恢复工作。（有关堆栈、尾部调用和非尾部调用的更透彻解释，请参阅Steele的论文，该论文揭穿了“昂贵的过程调用”的神话，或被认为有害的过程调用实现，或Lambda:the Ultimate GOTO，链接自readscheme.org的Lambda papers页面。）

但是Racket（以及许多其他方案和一些其他语言）实现了“堆栈”，这样即使有深度递归，也不会耗尽堆栈空间。换句话说，球拍没有堆栈溢出。其中一个原因是，支持深度递归的技术与支持一类连续性的技术是一致的，Scheme标准也需要这种技术。您可以在Clinger等人的《第一类连续性的实现策略》中阅读到这些内容。

Answer 2

方案需要消除尾调用。不是尾调用递归的代码将需要额外的堆栈帧。

暂时让我们假设javascript支持尾部调用优化，第二个函数定义将只使用一个堆栈帧，而第一个函数定义由于，将需要额外的堆栈帧。

function sum(n) {
   if (n === 0)
      return n;
   return n + sum(n - 1);
}

function sum(n) {
  function doSum(total, n) {
    if (n === 0)
       return total;
    return doSum(total + n, n - 1);
  }
  return doSum(0, n);
}

通过将计算结果放在堆栈上，可以编写许多递归函数来进行尾部调用优化

第一个定义的概念调用如下所示

3 + sum(2)
3 + sum(2) = 3 + 2 + sum(1)
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0)
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 3 + 2 + 1 + 0
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 6
3 + sum(2) = 3 + 2 + sum(1) = 6
3 + sum(2) = 6
6

第二个定义的调用如下所示

sum(3, sum(2)) = sum(5, sum(1)) = sum(6, sum(0)) = 6