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).

Answer 2

Yes, it is possible, if you introduce a helper function that takes an extra parameter:

-- calculate factor*(n choose k)
binom_and_multiply factor n 0 = factor
binom_and_multiply factor 0 k = 0
binom_and_multiply factor n k = binom (n-1) (k-1) (factor * n `div` k)

binom n k = binom_and_multiply 1 n k

The last line could be rewritten in point-free style:

binom = binom_and_multiply 1

---

EDIT: The function above shows the idea, but is actually broken, because the div operand truncates and opposed to the original version, there is no mathematical proof that the value to divide always is a multiple of the denominator. So that function must be replaced by the suggestion by Petr Pudlák:

-- calculate (n choose k) * num `div` denom
binom_and_multiply num denom _ 0 = num `div` denom
binom_and_multiply _   _     0 _ = 0
binom_and_multiply num denom n k = binom_and_multiply num denom (num * n) (denom * k) (n-1) (k-1)

binom = binom_and_multiply 1 1

---

In non-optimizing haskell implementations, you might be disappointed that the "properly tail recursive" variant still gobbles up lots of memory if you choose high values for n and k, because you are trading stack space in the non tail-recursive implementation by heap-space, as haskell is too lazy to calculate all the products just in time. It waits until you really need the value (maybe to print it), and just stores a representation of the two product expressions on the heap. To avoid that, you should make binom_and_multiply as they say strict in the first and second parameter, so the product will be eagerly evaluated while doing the tail recursion. For example, one could compare num and denom to zero, which will need to evaluate the expression for factor before going on:

-- calculate (n choose k) * num `div` denom
binom_and_multiply 0 0 _ _ = undefined  -- can't happen, div by zero
-- remaining expressions go here.

The general way to make sure the product is not "evalutated to large" is using the seq function:

-- calculate (n choose k) * num `div` denom
binom_and_multiply num denom _ 0 = num `div` denom
binom_and_multiply _   _     0 _ = 0
binom_and_multiply num denom n k = 
      new_num = num*n
      new_denom = denom*k
    in new_num `seq` new_denom `seq` binom_and_multiply new_num new_denom (n-1) (k-1)

This tells the haskell implementation that the recursive call to binom_and_multiply may only occur after new_num and new_denom has been evaluted (to WHNF, but explaining WHNF is out-of-scope for this question).

One last remark: What this answer was doing is called generally transforming a right-fold into a left-fold and then making the left-fold strict.