C语言如何判断函数是否为尾递归？示例代码求判定及原因说明

尾递归的核心特征是：函数执行的最后一步仅为递归调用自身，调用的返回值直接作为当前函数的返回值，不存在任何额外运算（算术运算、逻辑运算、赋值操作等），也不需要保留当前函数的栈帧数据等待递归返回后再处理。
C语言场景下判断可以直接遵循两个判断点：

• 递归调用是函数退出前的最后一个可执行操作
• 递归调用的返回值不需要参与任何运算，直接被返回

你编写的list_size_count函数不符合尾递归要求，核心原因如下：

struct link 
{
  int value; //data    
  link_t *next; //link
};

struct list
{
    link_t *first;
    link_t *last;
};

int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    // 问题点：递归调用结束后，还需要执行 acc + 递归返回值 的加法操作，才能得到当前函数的返回值
    // 程序必须保留当前栈帧中的acc值，等递归调用完成后做加法，无法触发尾递归优化
    return (acc + list_size_count((first->next), 1));
  }
  return acc;
}

int linked_list_size(list_t *list)
{
  return list_size_count((list->first),0);
}

上述代码的递归逻辑虽然能算出正确的链表长度，但额外的加法操作打破了尾递归的要求。如果需要改写为尾递归版本，可以参考如下实现：

int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    // 累加逻辑提前放到参数中传递，最后一步仅执行递归调用，返回值直接作为当前函数返回值
    return list_size_count(first->next, acc + 1);
  }
  return acc;
}

改写后的版本满足尾递归的所有特征，编译器开启优化选项（如O2）时会直接将递归转化为循环执行，不会出现递归深度过高导致的栈溢出问题。

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