Is this tail recursive?

Question

Per my understanding of tail recursion, the following function is not a tail recursive function.

(define (map f L)
  (if (null? L)
    '()
    (cons (f (car L)) (map f (cdr L)))))

cons will have to wait until (map f (cdr L)) returns to finish its job. That prevents it from being tail recursive.

Am I right?

Answer 1

Yes, it's not tail recursive.

Tail recursion is when the recursive call is in the tail position. The call to generate the return should be the original function or a mutually tail recursive function like so

(define (even? int)
  (if (= 0 int) #t (odd? (- int 1))))

(define (odd? int)
  (if (= 1 int) #t
      (if (= 0 int) 
          #f
          (even? (- int 1)))))

Answer 2

Yes!

That answer apparently wasn't long enough for Stack Exchange.

Yes, with a cherry on top!

Answer 3

It is safe to assume that it is not tail recursive since the standard (RNRS, including the latest R7RS) doesn't require tail recursion modulo cons optimization.

That of course doesn't deny anyone from actually implementing TRMCO in their Scheme implementation so that your definition of map, which is almost tail recursive (except for that cons), really would become tail recursive. Such an implementation could achieve this by transforming your code to something similar to the code below:

#!r6rs
(import (except (rnrs) map)
        (rnrs mutable-pairs))

(define (map fun lst)
  (define result (cons 'head '()))
  (let loop ((tail result) (lst lst))
    (cond ((null? lst) (cdr result))
          (else (set-cdr! tail (cons (fun (car lst)) '()))
                (loop (cdr tail) (cdr lst))))))

The transformation is pretty straightforward so I really don't see why Scheme implementations don't do it automatically, when Prolog does. It's less complex than what an implementation needs to do to support syntax-rules or call-with-current-continuation.