scheme - Scheme 中的递归函数是否总是尾调用优化？

Question

我在 Scheme 中读过一些关于尾调用优化的文章。但我不确定我是否理解尾调用的概念。如果我有这样的代码：

(define (fac n)
  (if (= n 0)
      1
      (* n (fac (- n 1)))))

可以对此进行优化，使其不会占用堆栈内存吗？或者尾调用优化只能应用于这样的函数：

(define (factorial n)
    (let fact ([i n] [acc 1])
      (if (zero? i)
          acc
          (fact (- i 1) (* acc i)))))

score 10 · Accepted Answer

考虑尾调用的一个有用方法是询问“递归过程调用的结果必须发生什么？”

第一个函数不能进行尾部优化，因为必须使用内部调用的结果fac，并乘以n产生对的整体调用的结果fac。

然而，在第二种情况下，“外部”调用fact的结果是……内部调用的结果fact。不需要对它做任何其他事情，后一个值可以简单地作为函数的值直接传回。这意味着不必保留其他函数上下文，因此可以简单地将其丢弃。

R5RS 标准通过使用尾部上下文的概念来定义“尾部调用” ，这基本上就是我上面所描述的。

score 4 · Accepted Answer

不，第一个fac无法优化。

调用函数时，您需要知道调用它的位置，以便在调用完成后返回该位置，并在将来的计算（fac函数）中使用调用结果。

fact实施方式不同。最后一件事fact就是调用它自己。无需记住我们调用的位置——相反，我们可以执行尾调用消除。fact退货后无需执行其他操作。

2 回答 2