在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)))))

- Moe

Answer 1

关于尾调用的一个有用的思考方式是：询问“递归过程调用的结果必须发生什么？”

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

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

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

- Norman Gray

Answer 2

不，第一个fac无法进行优化。

当调用函数时，需要知道它被调用的位置，以便在调用完成后返回该位置并在以后的计算中使用调用结果（一个fac函数）。 fact的实现方式不同。 fact所做的最后一件事是调用自身。没有必要记住我们正在调用的位置-相反，我们可以执行尾递归消除。在fact返回后不需要执行任何其他操作。

- Oleg Pavliv