我有一个在 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每一步(据我所知 Rational
在幕后执行)。
关于haskell - Haskell中的尾递归二项式系数函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28896626/