Scheme 中的递归函数总是尾部调用优化吗？
我读过一些关于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)))))
I've read something about tail-call optimization in Scheme. But I'm not sure whether I understand the concept of tail calls. If I have code like this:
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
can this be optimized, so that it won't take stack memory?
or can tail-call optimization only be applied to a function like this:
(define (factorial n)
(let fact ([i n] [acc 1])
(if (zero? i)
acc
(fact (- i 1) (* acc i)))))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
考虑尾部调用的一个有用方法是问“递归过程调用的结果必须发生什么？”
第一个函数无法进行尾部优化，因为必须使用对
fac内部调用的结果，并乘以n来生成对fac的整体调用的结果。然而，在第二种情况下，对
fact的“外部”调用的结果是...对fact的内部调用的结果。不需要对它做任何其他事情，后一个值可以简单地作为函数的值直接传回。这意味着不需要保留其他函数上下文，因此可以简单地丢弃它。R5RS 标准通过使用尾部的概念来定义“尾部调用”上下文，这基本上就是我上面所描述的。
A useful way to think about tail calls is to ask "what must happen to the result of the recursive procedure call?"
The first function cannot be tail-optimised, because the result of the internal call to
facmust be used, and multiplied bynto produce the result of the overall call tofac.In the second case, however, the result of the 'outer' call to
factis... the result of the inner call tofact. Nothing else has to be done to it, and the latter value can simply be passed back directly as the value of the function. That means that no other function context has to be retained, so it can simply be discarded.The R5RS standard defines 'tail call' by using the notion of a tail context, which is essentially what I've described above.
不，第一个
fac无法优化。当调用函数时，您需要知道调用它的位置，以便在调用完成后可以返回到该位置并在将来的计算中使用调用的结果（a
fac功能）。fact的实现方式不同。fact所做的最后一件事是调用自身。无需记住我们调用的位置 - 相反，我们可以执行尾调用消除。fact返回后无需执行任何其他操作。No, the first
faccannot be optimized.When a function is called, you need to know the place it was called from, so that you can return to that location once the call is complete and use the result of the call in future computations (a
facfunction).factis implemented differently. The last thing thatfactdoes is to call itself. There is no need to remember the place we are calling from — instead, we can perform tail call elimination. There is no other actions which should be done after thefactreturns.