我的练习，你可以在这里看到，说我需要实现C(n，k(的递归版本。
这就是我的解决方案：
module LE1.Recursao.Combinacao where
combina :: Integral a => a -> a -> a
combina n k | k == 0 = 1
| n == k = 1
combina n k | k > 0 && n > k = (combina (n - 1) k) + (combina (n - 1) (k - 1))
combina _ _ = 0
现在我想创建这个函数的尾部递归版本，这样我就不会得到大数字的堆栈溢出，也可以更快地计算组合！
我是尾调用优化的新手，但我在Fibonacci系列的Elixir中做到了这一点：
defmodule Fibonacci do
def run(n) when n < 0, do: :error
def run(n), do: run n, 1, 0
def run(0, _, result), do: result
def run(n, next, result), do: run n - 1, next + result, next
end
我理解这个Fibonacci代码，我认为组合算法没有太大区别，但我不知道如何开始。
传统实现如下所示：
combina n k = product [n-k+1 .. n] `div` product [1 .. k]
对于你想输入的大数字，它会立即运行，对于比你想输入大的数字，它运行得相当快。
> :set +s
> combina 40000 20000
<answer snipped because it's way too big to be useful>
(0.74 secs, 837,904,032 bytes)
同时，对于您的实现，combina 30 15花费了7秒，combina 40 20花费的时间比我愿意等待的要长——至少需要几分钟，甚至可以使用优化而不是解释进行编译。
通过选择巧妙的乘法和除法顺序，可以获得比这更高效的效率，但可读性明显较差。
Daniel Wagner的答案(或者我的其他答案，或者类似的东西(在实践中是正确的。但是，如果你想使用问题集中描述的重复周期，但又想让函数在合理的时间内运行，你就必须以不同的方式构建解决方案。考虑一些不在基本情况附近的n和k会发生什么。
combina n k
= combina (n - 1) k + combina (n - 1) (k - 1)
= combina (n - 2) k + combina (n - 2) (k - 1)
+ combina (n - 2) (k - 1) + combina (n - 2) (k - 2)
查看此处combina (n - 2) (k - 1)是如何计算两次的？此过程重复多次，导致您的算法占用指数时间。哎哟你怎么能解决这个问题？想象一下，制作一个包含combina所有结果的表。现在，您可以沿着表的每一行来计算下一行，从而避免重复的工作。这实际上只是计算Pascal的三角形。
combina :: Int -> Int -> Integer
combina n k
| k > n || k < 0 = 0
| otherwise = build n !! n !! k
step :: [Integer] -> [Integer]
step xs = 1 : zipWith (+) xs (drop 1 xs) ++ [1]
build :: Int -> [[Integer]]
build n0 = go (n0 + 1) [1]
where
go 0 _ = []
go n row = row : go (n - 1) (step row)
关键思想是在step中，它根据前一行计算每一行。
Daniel Wagner编写
combina n k = product [n-k+1 .. n] `div` product [1 .. k]
对于大型CCD_ 9和中型CCD_；乘法运算变得很大。我们如何才能让它们变小？我们可以写一个简单的递归：
combina :: Integer -> Integer -> Integer
combina n k
| k > n || k < 0 = 0
| otherwise = combina' n k'
where
-- C(n,k) and C(n,n-k) are the same,
-- so we choose the cheaper one.
k' = min k (n-k)
-- Assumes 0 <= k <= n
combina' _n 0 = 1
combina' n k
= -- as above
product [n-k+1 .. n] `div` product [1 .. k]
= -- expanding a bit
(n-k+1) * product [n-k+2 .. n] `div` (product [1 .. k-1] * k)
= -- Rearranging, and temporarily using real division
((n-k+1)/k) * (product [n-(k-1)+1 .. n] / product [1 .. k-1]
= -- Daniel's definition
((n-k+1)/k) * combina' n (k-1)
= -- Rearranging again to go back to integer division
((n-k+1) * combina' n (k-1)) `quot` k
综合来看，
combina' _n 0 = 1
combina' n k = ((n-k+1) * combina' n (k-1)) `quot` k
只剩下一个问题：这个定义不是尾递归的。我们可以通过向上计数而不是向下计数来解决这个问题：
combina' n k0 = go 1 1
where
go acc k
| k > k0 = n `seq` acc
| otherwise = go ((n-k+1)*acc `quot` k) (k + 1)
不用担心n `seq`；这无关紧要。
请注意，此实现使用O(min(k,n-k))算术运算。因此，如果k和n-k都很大，则需要很长时间。我不知道在这种情况下是否有任何有效的方法来获得确切的结果；我相信这类二项式系数通常是估计出来的，而不是精确计算出来的。