Haskell中的尾递归二项式系数函数

Question

我有一个函数来计算Haskell中的二项式系数,它看起来像这样:

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

是否可以修改它并使其尾递归？

Answer 1

是.有一个使用累加器来实现尾递归的标准技巧.在您的情况下,您将需要其中两个(或累积一个有理数):

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)

更新:对于大二项式系数,更好地使用,Integer因为Int很容易溢出.此外,在上述简单实现中,分子和分母都可以比最终结果大得多.一个简单的解决方案是积累Rational,另一个是在每一步都将它们的gcd分开(AFAIK Rational在幕后进行).