Scheme 中的递归和调用堆栈

Question

我是一名大学生，正在学习 Racket/Scheme 和 C 作为我 CS 学位的入门类(class)。

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

现在像Scheme这样的函数式语言，无时无刻不在使用递归。我知道尾递归在 Scheme 中是一个巨大的好处，据我所知，无论递归进行多深，它只需要一个堆栈框架(有人能澄清一下吗？)。

我的问题是:非尾递归呢？每个功能应用程序是否都保存在调用堆栈中？如果我能简要了解这是如何工作的，或者给我指出一个资源，我将不胜感激；我似乎无法在任何地方找到明确说明这一点的地方。

Answer 1

Scheme要求尾调用消除。非尾调用递归的代码将需要额外的堆栈框架。

暂时让我们假设 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 + 03 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 63 + sum(2) = 3 + 2 + sum(1) = 63 + sum(2) = 66

第二个定义的调用看起来像这样

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