Tail recursive binomial coefficient function in Haskell

Question

I have a function that calculates the binomial coefficient in Haskell, it looks like this:

binom :: Int -> Int -> Int
binom n 0 = 1
binom 0 k = 0
binom n k = binom (n-1) (k-1) * n `div` k

Is it possible to modify it and make it tail recursive?

Answer 1

Yes. There is a standard trick of using an accumulator to achieve tail recursion. In your case, you'll need two of them (or accumulate one rational number):

binom :: Int -> Int -> Int
binom = loop 1 1
  where
    loop rn rd _ 0 = rn `div` rd
    loop _  _  0 _ = 0
    loop rn rd n k = loop (rn * n) (rd * k) (n-1) (k-1)

Update: For large binomial coefficients, better use Integer as Int can easily overflow. Moreover in the above simple implementation both numerator and denominator can grow much larger than the final result. One simple solution is to accumulate Rational, another would be to divide both by their gcd at every step (which AFAIK Rational does behind the scenes).