Haskell - counting number of recursions

Question

I have a simple function that calculates the n-th fibonnaci number below:

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

But i am interested in a way to count the number of recursions of this function. Any ideas how to do it?

Answer 1

This puts one in mind of sigfpe's illustration of the so-called Writer monad. You might do it a bit more systematically like this:

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 thus:

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

This is the same definition, but with the 'side effect' of logging each additional pair of recursions. We can also add a side effect in IO if we want to see all the crazy recalculation involved in the 'naive' definition while it 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 repetitious show, as the calculation climbs toward 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})

Answer 2

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

For the base cases, there are no recursions, for everything else, we have two direct recursive calls and those that are invoked from the two.

You can also re-use the fibonacci code,

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