recursion - 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”语句中的第二个参数返回，然后才能计算 bool 值表达。相反，对于 ascending-tail-helper，我可以在执行递归调用之前评估小于表达式。

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

Answer 1

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

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

来自手册:

Tail Calls: Any sub-expression that is (syntactically) in tail-position with respect to its enclosing context is annotated by drawing a light purple arrow from the tail expression to its surrounding expression.