递归调用是否必须严格是函数中的最后一次调用才能使函数成为尾递归？

Question

受到Reddit上一篇帖子的启发（有人想统计commonlisp论坛中的频率），我想写一个基于列表的帖子以供娱乐和练习，基于哈希的当然更高效。我第一个得到这个：

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

我认为它不是尾递归，因为它通过调用另一个函数来调用自身，所以我像这样重写了它：

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

但是，当我查看 SBCL 中生成的汇编代码时，两者似乎都经过优化，在优化编译时，递归函数调用被删除并替换为循环。制作出来的组装不一样，第一个有点长。

那么到底是怎么回事呢？即使函数不是尾递归，或者两者都是尾递归，也只需 SBCL 执行优化？

对自身的调用是否必须严格是函数中的最后一条语句才能使函数成为尾递归？

Answer 1

按照@Barmar 的评论，第一步可能如下所示 -

(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

可以进一步优化使用尾递归模cons（trmc）。