5

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

(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”语句中的第二个参数返回，然后才能计算布尔表达式。相反，对于升尾助手，我可以在进行递归调用之前评估小于表达式。

这是正确的，还是我让自己比以前更加困惑？

4

4 回答 4

7

DrRacket 可以帮助您确定呼叫是否处于尾部位置。单击“语法检查”按钮。然后将鼠标指针移动到相关表达式的左括号。在您的示例中，我得到了这个：

在此处输入图像描述

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

从手册：

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

于 2012-10-17T11:49:29.930 回答
6

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

但是，and是一个宏，通常使用if

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

这是尾递归。

于 2012-10-17T00:25:56.373 回答
0

函数处于尾部位置的要求之一是它的返回值可以用作父函数的返回值，而无需修改或检查。也就是说，父函数应该能够在评估完尾部位置语句后立即返回。

第一次出现时，您的第一个函数会检查升序的返回值。似乎不会返回升序的值，而是从它派生的值。 但是，根据 R5RS 规范的相关部分，and语句中的最终表达式位于尾部位置。（当我清醒时，我知道这一点）

所以你错了。

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

（注意：已编辑以纠正我最初的仓促回答）。

于 2012-10-17T00:26:39.983 回答
0

球拍关于尾部位置的文档说，检查尾部位置和不在尾部位置的地方是特定表格的文档：

尾部位置规范为计算的渐近空间消耗提供了保证。通常，尾部位置的规范与每种句法形式一致，例如if.

Racket's docs on and say (强调添加)：

(and expr ...)

如果没有提供 expr，则结果为 #t。

如果提供了单个 expr，则它位于 tail 位置，因此 和 expression 的结果是 expr 的结果。

否则，将评估第一个 expr。如果它产生#f，and 表达式的结果是#f。否则，结果与 and 表达式相同，剩余的 expr 相对于原始 and 形式位于尾部位置。

于 2015-11-17T18:11:41.593 回答