球拍：识别尾递归？-Java 学习之路

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

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

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

但是， and 是一个宏，通常使用 if 进行扩展
```
(define (ascending list)
  (if (<= (length list) 1)
      #t
      (if (< (car list) (car (cdr list)))
          (ascending (cdr list))
           #f)))
```
这是尾递归 .
回复于 2024-04-19T21:24:43+08:00
0

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

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

从手册：

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

回复于 2024-04-19T21:24:43+08:00
7

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

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

所以你错了 .

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

（注意：编辑以纠正我最初仓促的答案） .

回复于 2024-04-19T21:24:43+08:00
6

Racket的documentation on tail positions表示检查's in tail position and what'不是特定表格的文档的地方：

尾部位置规范提供了关于计算的渐近空间消耗的保证 . 一般来说，尾部位置的规范与每种句法形式一致，如果 .

Racket's docs on and说（重点补充）：

（和expr ......）
如果没有提供exprs，则结果为#t . 如果提供了单个expr，那么它处于尾部位置，因此和表达式的结果是expr的结果 . 否则，将评估第一个expr . 如果它产生#f，则表达式的结果为#f . 否则，结果与a和表达式相同，其中尾部位置的剩余exprs相对于原始和形式 .

回复于 2024-04-19T21:24:43+08:00

球拍：识别尾递归？

4 回答

相关问题