2

我看到以下两个函数在语法上都是尾递归函数，但是，在球拍中，它们中的哪一个真正被视为尾递归，或者两者兼而有之？我的意思是它是否被解释器优化为尾递归。

;;1
(define (foo i m s)
    (if (< i m)
        (foo (+ i 1) m (+ i s))
        s))

;;2
(define (foo i m s)
    (if (= i m)
        s
        (foo (+ i 1) m (+ i s))))

其他 lisps有什么不同的答案吗？

4

4 回答 4

4

两者都是尾递归的，因为递归调用是在尾部位置完成的，也就是说：这是调用递归时完成的最后一件事。if如果在所示过程中颠倒了表达式中后件和替代部分的顺序，则完全没有关系。

根据 Scheme 的规范，所有尾递归都必须优化掉，无论它们出现在代码中的什么位置，从语法上讲：

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

于 2013-03-17T15:59:41.397 回答
3

只要我们在谈论Scheme：没有。所有符合要求的实现都需要检测尾调用并进行适当的优化，因此这些实现只需要一个恒定的堆栈空间。在您的示例中，两者都是完全有效的 tail-calls，并且必须被任何符合要求的实现识别为这样。

另一方面，如果我们谈论的是“一般的 Lisp”，那么情况就不同了。例如， ANSI Common Lisp不需要符合规范的实现来专门处理尾调用。尽管大多数现代实现确实可以识别尾调用（并且会在声明的正确组合下优化它们），但语言本身没有任何东西可以保证这种行为。

于 2013-03-17T15:57:54.513 回答
3

Scheme R7RS 草案 8第 11 页的第 3.5 节根据句法形式确定了所有尾递归要求。因为if要求是：

(if expression <tail expression> <tail expression>)
(if expression <tail expression>)

因此，根据您的代码示例并假设 Racket 忠实于 Scheme，两者都是尾递归的。至于其他 lisp，我不认为 Common Lisp 需要尾递归优化。

于 2013-03-17T16:36:12.510 回答
0

emacs lisp 没有优化尾递归：

(defun fact (n &optional result)
  (unless result (setq result 1))  ; use 1 if not given
  (if (zerop n) result
     (fact (1- n) (* n result))))
(fact 12)
479001600
(fact 1000)
Lisp nesting exceeds max-lisp-eval-depth

（不要介意这个值是一个固定的整数，所以你不能为 1000 返回一个准确的值！无论如何 -(fact 30)工作但返回一个错误的值。）

为了补充之前的通讯员所说的内容，实现可以自由地优化更高optimization级别和/或更低级别的尾递归safety。如果有疑问，请尝试不同的值并(disassemble 'foo) 尝试(trace foo)- 如果尾递归未优化，您应该在调用它时看到每个调用，如果是，您应该只看到“顶部”调用。

于 2013-03-22T14:07:52.783 回答