我有一个函数可以计算Haskell中的二项式系数，它看起来像这样：
binom :: Int -> Int -> Int
binom n 0 = 1
binom 0 k = 0
binom n k = binom (n-1) (k-1) * n `div` k
是否可以修改它并使它尾部递归？
是。使用累加器实现尾递归是一个标准技巧。在您的情况下，您将需要两个（或累积一个有理数）：
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除以（AFAIKRational在后台执行此操作）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句