带守卫（Guards）的函数是否为尾递归？以elem'实现为例求证

好问题！先给你明确结论：带守卫的函数完全可以是尾递归，你提供的elem'实现也确实是尾递归的。

先搞清楚尾递归的核心判断标准 #

尾递归的关键是：函数的最后一个执行操作就是递归调用自身，递归调用返回后，当前函数不需要再做任何额外的计算（比如算术运算、数据构造、逻辑组合等），直接把递归结果作为自己的返回值。

分析你的elem'实现 #

我们逐分支看你的代码：

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys)
    | x == y = True
    | otherwise = elem' x ys

• 第一个模式elem' x [] = False：直接返回常量，没有递归，自然没问题。
• 第二个模式的守卫分支：
  • 第一个守卫x == y = True：直接返回布尔值，没有递归操作。
  • 第二个守卫otherwise = elem' x ys：这里递归调用elem' x ys是这个分支的最后一步操作——函数直接把递归调用的结果返回，没有任何后续处理（比如不会把递归结果和其他值做运算、包装等），完全符合尾递归的定义。

再补充一点：守卫不影响尾递归的判定 #

守卫只是Haskell里的条件分支语法，本质和if-else没区别。只要每个分支的最后一步满足尾递归的要求，不管用不用守卫，函数都是尾递归的。比如如果把你的代码改成if-else形式：

elem' x (y:ys) = if x == y then True else elem' x ys

这显然也是尾递归，和用守卫的版本逻辑完全一致。

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