CODEWITHSUNDEEP
haskellrecursion
MackProgram
MackProgram

Reputation: 77

How to use recursive in Haskell

I'm trying to understand how recursion works in haskell, I'm trying to do a function that multiply using a sum

Something like 4 * 5 = 4 + 4 + 4 + 4 + 4

My current function is

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

if I try to do multiplicacao 7 3 it returns 28

Upvotes: 1

Views: 131

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476624

The problem is here that you recurse with (a+a) as new value to multiply. Indeed, if you for example use multiplicacao 7 3, you get:

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

each recursive step, you thus multiply a with 2 and subtract one from b, so that means that you are calculating a×2b-1.

You should keep the original a and thus each time add a to the accumulator. For example with:

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)

This will only work if b is a natural number (so zero or positive).

You can however work with an implementation where you check if b is even or odd, and in the case it is even multiply a by two. I leave this as an exercise.

Upvotes: 2

Related Questions