球拍:识别尾递归？

Question

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

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

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

Answer 1

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

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

从手册:

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

Answer 2

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

但是,and是一个宏,并且通常使用扩展if

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

这是尾递归.