为什么在Scheme的所有实现中都需要尾递归？

Question

为什么在Scheme的所有实现中都需要尾递归？

schemetail-recursion

3

尾递归更高效，因为它重复使用同一堆栈帧而不是创建一个新的，但为什么在scheme中这对所有内容都是必需的呢？

- omega

因为你刚才说的话，请等一下。在Scheme中，并非“所有东西都必须是尾递归”的要求，但需要正确实现尾递归，因为尾递归在Scheme中被广泛使用。此外，由于没有尾递归将不可能使用call/cc。 - Will Ness

没有尾调用就不能使用call/cc吗？我不明白你为什么这样说。 - John Clements

@JohnClements 我的意思是说“如果没有正确的TR，就无法使用它”。调用call/cc应该会倒回调用堆栈；但是没有TR，对函数的调用将保留其调用堆栈。因此，即使您允许它，也会出现堆栈溢出。这就是我的想法。 - Will Ness

1

@WillNess：哦...我想你的意思是“使用call/cc捕获的续延调用应该重置调用栈”...我同意，但尾调用/尾递归与此无关；您可以拥有一个非尾调用语言，仍然允许由于使用续延而引起的堆栈操作。事实上，Rhino是一个开源JavaScript实现，它不是尾调用的，但具有续延捕获和调用机制。 - John Clements

@JohnClements 很有趣，我不知道这一点（是的，这就是我的意思... :) ），那么在Rhino中调用捕获的 continuation 和普通调用是不同的，对吗？我会再读一些相关内容，谢谢。 :) - Will Ness

3个回答

2

尾递归在语言规范中被强制执行。引用自R6RS的第5.11节：

“Scheme语言的实现必须是正确的尾递归。在某些句法上下文中发生的过程调用称为尾调用。如果支持无限数量的活动尾调用，则Scheme实现是正确的尾递归。如果被调用的过程仍然可能返回，则调用是活动的。请注意，这包括常规返回以及通过先前捕获的call-with-current-continuation进行返回的返回。在没有捕获到continuations的情况下，调用最多只能返回一次，而活动调用将是尚未返回的调用。有关适当尾递归的正式定义可以在Clinger的论文[5]中找到。从(rnrs base(6))库中识别尾调用的规则在第11.20节中描述。”

这样做的实际原因是，尾递归允许使用递归实现高效的循环。

- Óscar López

0

没有TR的保证，call/cc将无法使用。循环本身可以通过do（它是语言的一部分）来实现。

编辑：这被证明是不正确的。请参见John Clements在问题中的评论。一种语言可以具有非TR函数调用机制，但具有单独的特殊机制来调用连续体。

- Will Ness

说到这里，这里有一个尾递归的例子：http://instagram.com/p/NObwZSkEAk/ ；-) - C. K. Young

1

@ChrisJester-Young 很不错！ :) 嘿，这是你的！ - Will Ness

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- C. K. Young · Accepted Answer

Scheme没有goto，因此所有的循环最终都是使用尾递归完成的。如果没有完备的尾递归保证，就没有可靠的方式来提供Scheme中的循环。

更新: 我想解释一下我所说的"最终使用尾递归"。让我们看看do宏，因为@newacct提到了它。例如:

(do ((i 1 (+ i 1)))
    ((> i 10))
  (display i)
  (newline))

正如我所提到的，Scheme 没有 goto，因此它必须从其他地方获取循环。它实际上是通过宏展开得到（类似于）这个：

(let loop ((i 1))
  (unless (> i 10)
    (display i)
    (newline)
    (loop (+ i 1))))

请注意，这里的loop并不是关键字或内置函数。它是通过命名的let^†创建的命名函数，并在unless表单底部通过尾递归调用。

实际上，在Scheme中，所有标准循环形式都使用尾递归。无法摆脱尾递归的影响。

† 这是命名let（口语上^‡）的宏展开：

(letrec ((loop (lambda (i)
                 (unless (> i 10)
                   (display i)
                   (newline)
                   (loop (+ i 1))))))
  (loop 1))

严格来说，它会被宏展开为：

((letrec ((loop (lambda (i)
                  (unless (> i 10)
                    (display i)
                    (newline)
                    (loop (+ i 1))))))
   loop)
 1)