Racket: Identifying tail recursion?

Question

I wrote two different functions in racket to determine whether a list of numbers is ascending:

(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))))

I had the hardest time determining whether or not the first ascending was tail recursive, so I rewrote it using what I believe to be tail recursion.

The reason why I retrospectively believe the first one to not be tail recursive is that I believe at each level of recursion, the function will be waiting for the second argument in the "and" statement to return before it can evaluate the boolean expression. Conversely, for ascending-tail-helper, I am able to evaluate the lesser than expression before I do my recursive call.

Is this correct, or did I make myself even more confused than before?

Answer 1

DrRacket can help you determine whether a call is in tail position or not. Click the "Syntax Check" button. Then move the mouse pointer to the left parenthesis of the expression in question. In your example I get this:

The purple arrow shows that the expression is in tail-position.

From the manual:

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.

Answer 2

You are correct, in the first version the recursive call returns to and, whereas in the second version the recursive call is a tail call.

However, and is a macro, and is generally expanded using if

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

which is tail recursive.