Racket：如何识别尾递归？

Question

我在Racket中编写了两个不同的函数来确定数字列表是否升序：

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (and (< (car list) (car (cdr list))) (ascending (cdr list)))))

(define (ascending-tail list)
  (ascending-tail-helper #t list))

(define (ascending-tail-helper prevBool rest)
  (if (<= (length rest) 1)
      prevBool
      (ascending-tail-helper (and prevBool (< (car rest) (car (cdr rest)))) (cdr rest))))

我曾经花费很长时间来确定第一个升序函数是否是尾递归，所以我重新编写了它，使用我认为是尾递归的方式。

我回顾后认为第一个函数不是尾递归的原因是，在每次递归的每个级别上，函数都将等待“and”语句中的第二个参数返回，然后才能计算布尔表达式。相反，在ascending-tail-helper中，我能够在进行递归调用之前计算小于表达式。

这个理解正确吗？还是让我比以前更困惑了？

- L.Neil

Answer 1

DrRacket可以帮助您确定调用是否处于尾部位置。点击“语法检查”按钮，然后将鼠标指针移动到所询问表达式的左括号上。在您的示例中，我得到了以下结果：

紫色箭头表示该表达式处于尾部位置。

根据手册：

尾调用：任何在其封闭上下文中（语法上）处于尾部位置的子表达式都会通过从尾部表达式到其周围表达式绘制浅紫色箭头进行注释。

- soegaard

---

Racket的文档还指出，and的最后一个参数处于尾位置。 - Joshua Taylor

Answer 2

您说得对，在第一个版本中，递归调用返回到and，而在第二个版本中，递归调用是尾调用。

然而，and是一个宏，通常使用if扩展。

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (if (< (car list) (car (cdr list)))
          (ascending (cdr list))
           #f)))

这是尾递归。

- Doug Currie

---

哦，哇！我完全不知道！那肯定能解释为什么函数在调试器中表现为尾递归。 - L.Neil

感谢让我保持警觉，道格 ;) - itsbruce

这段内容如果参考语言手册会更有说服力。在某些语言中，例如Scheme，and操作符的最后一个子句被明确规定为尾部上下文。也就是说，它的实现方式（作为宏、内置等）并不重要；最后一个位置就是尾部位置。目前的措辞让人觉得宏展开只是碰巧将最后一个子句放在了尾部位置，这是一种（幸运的）巧合。而Racket可能确实规定了它就是尾部位置。 - Joshua Taylor

刚在 Racket 文档中找到了这个。and 的最后一个参数处于尾部位置。 - Joshua Taylor

Answer 3

Racket的尾部位置文档指出，检查什么在尾部位置和什么不在尾部位置的地方是特定形式的文档：

尾部位置规范提供了有关计算渐近空间消耗的保证。一般来说，尾部位置的规范与每个语法形式一起使用，例如if。

Racket关于and的文档（重点添加）：

(and expr ...)

If no exprs are provided, then result is #t.

If a single expr is provided, then it is in tail position, so the results of the and expression are the results of the expr.

Otherwise, the first expr is evaluated. If it produces #f, the result of the and expression is #f. Otherwise, the result is the same as an and expression with the remaining exprs in tail position with respect to the original and form.

- Joshua Taylor

Answer 4

一个函数成为尾部位置的要求之一是，它的返回值可以在不经过修改或检查的情况下作为父函数的返回值使用。也就是说，父函数应该能够立即返回，已经评估了尾部位置语句。

乍一看，你的第一个函数检查了ascending的返回值。看起来它并没有返回ascending的值，而是从中派生出一个值。然而，根据R5RS规范的相关部分，and语句中的最后一个表达式确实处于尾部位置。(当我清醒时，我知道这一点)

所以你是错的。

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5

（注意：已编辑以更正我的初始匆忙回答。）

- itsbruce

---

谢谢。真正让我困惑的是，在DrRacket中调试非尾递归函数时，它没有正确地在“堆栈”窗格中保留调用堆栈；而在基本情况下，调试器没有跟随“and”评估；而是立即返回，就像尾递归函数一样！真的很令人困惑。 - L.Neil

不是这样的，@itsbruce，and是一个宏，它不检查它的第二个值，只有在第一个参数为真时才返回它；请参见我的答案以获取通常的展开。 - Doug Currie

啊，点着呢，道格。现在我回想起来了，“and”是通过宏实现的，不像“not”。我刚刚重新阅读的r5rs规范明确描述了这一点。 - itsbruce

实际上，实现方式并不重要。它可以是内置的、宏定义的或其他什么形式。重要的是规范是否说明它处于尾位置。在Scheme中，它是这样的（例如，文档所示）。我不知道Racket的情况。 - Joshua Taylor