如何在 Haskell 中使用递归

Question

我正在尝试了解递归在 haskell 中的工作原理，我正在尝试做一个使用 sum

相乘的函数

类似 4 * 5 = 4 + 4 + 4 + 4 + 4

我目前的职能是

multiplicacao a b 
    | b == 1 = a 
    | otherwise = multiplicacao (a + a) (b-1)

如果我尝试做 multiplicacao 7 3 it returns 28

Answer 1

这里的问题是您使用 (a+a) 作为要相乘的新值进行递归。事实上，如果你使用 multiplicacao 7 3，你会得到：

multiplicacao 7 3
  -> multiplicacao (7+7) (3-1)
  -> multiplicacao (7+7) 2
  -> multiplicacao ((7+7)+(7+7)) (2-1)
  -> multiplicacao ((7+7)+(7+7)) 1
  -> ((7+7)+(7+7))
  -> 14 + 14
  -> 28

每个递归步骤，您因此将 a 乘以 2 并从 b 中减去一个，因此这意味着您正在计算 a×2^b-1.

您应该保留原来的 a，因此每次都将 a 添加到累加器。例如：

multiplicacao :: (Num a, Integral b) => a -> b -> a
multiplicacao a = go 0
  where go n 0 = n
        go n b = go (n+a) (b-1)

这仅在 b 是 自然数 数字（即零或正数）时有效。

然而，您可以使用检查 b 是偶数还是奇数的实现，如果是偶数，则将 a 乘以二。我把它留作练习。

如何在 Haskell 中使用递归

How to use recursive in Haskell

recursion

haskell