haskell - Haskell 非尾递归

Question

我想知道这是否代表尾递归。如果不是，我该怎么做。

 countP :: [a] -> (a->Bool) -> Int
 countP [] _ = 0
 countP (x:xs) p = countP_aux (x:xs) p 0

 countP_aux [] _ _ = 0
 countP_aux (x:xs) p acumul
                        |p x==True = (countP_aux xs p (acumul))+1
                        |otherwise = (countP_aux xs p (acumul))

  countP [1,2,3] (>0)
  3
  (72 reductions, 95 cells)

此练习显示列表中有多少值由 p 条件验证。谢谢

Answer 1

这不是尾递归，因为

(countP_aux xs p (acumul))+1

尾调用应该返回递归调用的结果，而不是用递归调用的结果进行计算。

您可以使用执行附加工作的累加器将非尾递归函数转换为尾递归，即

假设您有一个简单的计数功能

f a
  | a < 1 = 0 
  | otherwise = f (a-1) + 1

您可以像这样使其尾递归：

f' acc a = 
  | a < 1 = acc 
  | otherwise = f' (acc + 1) (a-1)
f = f' 0