我如何在这个组合函数上使用尾调用优化？

Question

我的练习，你可以看到 here，说我需要 实现 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

现在我想创建这个函数的尾递归版本，这样我就不会遇到大数的堆栈溢出问题，并且可以更快地计算组合！

我是尾调用优化的新手，但我在 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

我理解这个斐波那契代码，我认为组合算法差别不大，但我不知道如何开始。

Answer 1

传统的实现是这样的：

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 花费的时间比我愿意等待的时间更长——至少几分钟，甚至是通过优化而不是解释进行编译。

通过选择巧妙的乘法和除法顺序可以获得比这更高的效率，但它的可读性要差得多。

Answer 2

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) 是如何计算两次的吗？此过程重复多次，导致您的算法花费 指数级 时间。哎哟。你怎么能解决这个问题？好吧，想象一下 table combina 的所有结果。现在您可以沿着 table 的每一行计算下一行，避免重复工作。这实际上只是在计算 帕斯卡三角形.

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 中，它根据前一行计算每一行。

Answer 3

丹尼尔瓦格纳写道

combina n k = product [n-k+1 .. n] `div` product [1 .. k]

对于大型 n 和中型 k，这可能会变得相当低效；乘法变得巨大。我们怎样才能让它们变小？我们可以写一个简单的递归：

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 都很大的话，需要很长时间。我不知道在这种情况下是否有任何有效的方法来获得准确的结果；我相信这种二项式系数通常是估计的而不是精确计算的。

我如何在这个组合函数上使用尾调用优化？

How I could use tail call optimisation on this combination function?

algorithm

haskell

recursion

combinations

tail-call-optimization