我有一个函数可以计算Haskell中的二项式系数,如下所示:

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


是否可以修改它并使它尾部递归?

最佳答案

是。使用an accumulator to achieve tail recursion有一个标准技巧。在您的情况下,您将需要两个(或累积一个有理数):

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(AFIAK Rational在后台执行此操作)。

09-17 15:05
查看更多