尾递归是否要求递归调用为函数最后调用？兼谈SBCL递归优化现象

受Reddit上一篇帖子启发（有人在Common Lisp论坛中想要统计频率），出于兴趣与练习编写了一个基于列表的频率统计实现（基于哈希表的实现效率更高）。最初的代码如下：

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

我认为该函数并非尾递归，因为其递归调用嵌套在cons函数调用中，于是将其重写为：

(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对非尾递归函数也进行了优化，还是这两个函数其实都是尾递归？此外，尾递归是否要求递归调用必须是函数中的最后一条语句？

1. 两个函数的尾递归判定 #

第一个函数不是严格尾递归：它的递归调用(count-frequences lst)被嵌套在cons操作中，函数返回前需要把当前计算的(cons elt ...)和递归调用的结果组合，递归调用的结果并非直接作为函数的返回值，不符合尾递归的定义。

第二个函数是严格尾递归：函数的返回值要么是freq，要么直接是递归调用(count-frequences lst freq)的结果，没有后续额外操作，满足尾递归要求。

2. SBCL对非尾递归的优化原因 #

SBCL的编译器具备超越严格尾递归的递归优化能力，它可以识别某些线性递归的模式（比如第一个函数这种“先处理当前元素，再递归处理剩余部分，最后将结果组合”的结构），将其转换为循环。这种优化不属于传统的尾调用消除，而是编译器对递归结构的深度分析与转换，目的是避免栈溢出并提升执行效率。

3. 尾递归的严格定义 #

严格来说，尾递归要求递归调用是函数最后执行的操作——函数的返回值必须直接等于递归调用的结果，不能在递归调用之后再进行任何计算（比如cons、算术运算、其他函数调用等）。递归调用是否是“最后一条语句”只是表面现象，核心是递归调用的结果是否直接作为函数的返回值，不需要额外处理。

4. 汇编代码长度差异的原因 #

第一个函数被转换为循环时，编译器需要额外处理结果链表的构建逻辑：原代码中每次递归都要将当前元素的频率节点cons到递归结果的头部，转换成循环后需要先收集所有节点，最后再调整链表结构（或在循环中维护链表的构建顺序），这会增加汇编代码的长度。

而第二个函数通过push直接在可选参数freq中累积结果，递归结束后直接返回该列表，转换为循环时逻辑更简洁，因此生成的汇编代码更短。

内容的提问来源于stack exchange，提问作者myname