Haskell中如何实现统计fib函数调用次数的callsFib函数？

你现有的递归斐波那契函数如下：

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib x
    | x < 0 = error "argumento negativo"
    | otherwise = fib (x - 1) + fib (x - 2)

要实现callsFib函数统计计算fib n时的总调用次数，我们可以基于递归逻辑推导：

• 计算fib 0或fib 1时，各自仅触发1次调用（直接匹配基准情况）
• 计算fib n（n≥2）时，会先触发1次自身调用，再加上计算fib(n-1)和fib(n-2)的总调用次数

据此可以写出callsFib的实现：

callsFib :: Integer -> Integer
callsFib 0 = 1
callsFib 1 = 1
callsFib x
    | x < 0 = error "负数参数"
    | otherwise = 1 + callsFib (x - 1) + callsFib (x - 2)

验证示例 #

以callsFib 3为例：

1. callsFib 3 = 1 + callsFib 2 + callsFib 1
2. callsFib 2 = 1 + callsFib 1 + callsFib 0 = 1 + 1 + 1 = 3
3. 代入后得到1 + 3 + 1 = 5，与预期结果一致

内容的提问来源于stack exchange，提问作者j.j.3