Does recursive call have to be strictly the last call in a function for a function to be tail-recursive?

Question

Inspired by a post on Reddit (someone wanted to count frequencies in commonlisp forum), I wanted to write a list-based one for the fun and practice, hash-based one is of course more efficient. I got this one first:

    (defun count-frequences (list)
      (let* ((len (length list))
             (elt (car list))
             (lst (delete elt list)))
        (if (null lst)
            (cons (cons elt (- len (length lst))) nil)
            (cons (cons elt (- len (length lst)))
                  (count-frequences lst)))))

I thought it wasn't tail-recursive, since it calls itself through a call to another function, so I re-wrote it like this:

    (defun count-frequences (list &optional freq)
      (let* ((len (length list))
             (elt (car list))
             (lst (delete elt list)))
        (push (cons elt (- len (length lst))) freq)
        (if (null lst)
            freq
            (count-frequences lst freq))))

However, when I look at the generated assembly code in SBCL, both seem to be optimized, with recursive function calls removed and replaced with loops, when compiled with optimizations. The produced assembly is not the same, and the first one is somewhat longer.

So what is going on? Just SBCL performing optimization even if a function is not tail-recursive, or are both tail recursive?

Does call to itself have to be strictly the last statement in the function for a function to be tail recursive?

Answer 1

Following @Barmar's comment, the first step might look like this -

(defun count-frequences (list)
  (let* ((len (length list))
         (elt (car list))
         (lst (delete elt list))
         (val (cons elt (- len (length lst))))) ;; refactor
    (if (null lst)
        (cons val nil)
        (cons val (count-frequences lst))))) ;; trmc

Which can be further optimized to using tail recursion modulo cons (trmc).