Haskell - recursion count

Question

I have a simple function that calculates the nth fionnasy number below:

fibonacci :: Integer -> Integer fibonacci 0 = 0 fibonacci 1 = 1 fibonacci n = (fibonacci (n-1) ) + (fibonacci (n-2)) 

But I'm interested in a way to count the number of recursions of this function. Any ideas how to do this?

Answer 1

 recursions :: Integer -> Integer recursions 0 = 0 recursions 1 = 0 recursions n = recursions (n-1) + recursions (n-2) + 2 

For basic cases, there are no recursions; for everything else, we have two direct recursive calls and those that are called from two.

You can also reuse the fibonacci code,

 recursions n = 2*fibonacci (n+1) - 2 

Answer 2

This calls into question sigfpe Illustration of the so-called Writer monad . You can do this a little more systematically:

 import Control.Monad.Trans.Writer import Control.Monad.Trans import Data.Monoid fibwriter :: Int -> Writer (Sum Int) Integer fibwriter 0 = return 0 fibwriter 1 = return 1 fibwriter n = do a <- fibwriter (n-1) b <- fibwriter (n-2) tell (Sum (2::Int)) return (a + b) 

Used this way:

 *Fib> runWriter $ fibwriter 11 (89,Sum {getSum = 286}) 

This is the same definition, but with a “side effect” of registering each additional pair of recursions. We can also add a side effect to IO if we want to see all the crazy recalculations involved in determining the naive when this happens:

 fibprint :: Int -> WriterT (Sum Int) IO Integer fibprint 0 = return 0 fibprint 1 = return 1 fibprint n = do a <- fibprint (n-1) record a b <- fibprint (n-2) record b return (a + b) where record x = lift (putStr $ ' ' : show x) >> tell (Sum 1) 

For fibonacci 11, this gives us this absurdly repeating show, as the calculation rises to 89:

 *Fib> runWriterT $ fibprint 11 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 13 34 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 55 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 13 34(89,Sum {getSum = 286})