recursion - Scheme和调用堆栈中的递归

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

我已经在线阅读了关于使用迭代而不是C中的递归的一般最佳实践，因为由于将堆栈帧保存到调用堆栈等中而使递归非常昂贵。

现在，在像Scheme这样的功能语言中，递归一直被使用。我知道尾递归在Scheme中是一个巨大的好处，据我了解，无论递归进行得有多深，它都只需要一个堆栈帧(有人可以澄清吗？)。

我的问题是:非尾递归如何？每个函数应用程序都保存在调用堆栈中吗？如果能简要了解它的工作原理或将其指向资源，我将不胜感激。我似乎找不到任何地方明确指出这一点。

最佳答案

Scheme要求取消尾叫。不是尾调用递归的代码将需要一个额外的堆栈框架。

暂时让我们假设javascript支持尾部调用优化，这些函数定义中的第二个将仅使用1个堆栈框架，而第一个(由于+的原因)将需要一个额外的堆栈框架。

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 +总和(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