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 回答