haskell - 如何计算这个 Haskell 函数中发生了多少递归调用？

Question

我已经尝试了几个小时来解决这个问题。我需要计算使用某个函数发生了多少递归调用:

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs)   
    | x > maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs  

在此先感谢

Answer 1

您可以重写您的函数以在一个额外的参数中携带有关递归深度的信息，并将其作为元组的第二个(或第一个，如果您愿意的话)元素返回:

maximum' :: (Ord a) => [a] -> Int -> (a, Int)
maximum' [] _ = error "maximum of empty list"  
maximum' [x] n = (x, n)
maximum' (x:xs) n   
    | x > fst maxTail = (x, snd maxTail)
    | otherwise = maxTail  
    where maxTail = maximum' xs (n + 1)

然后您可以使用 maximum' lst 0 或 maximum' lst 1 调用函数，具体取决于您是否希望第一次调用计为递归级别。

可以使用任何递归函数来完成，但在您的情况下可能没有必要。正如 chepner 所写，无需额外计算即可知道答案。