How to use recursive in Haskell

Question

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

You are missing an else branch. In Haskell, it is a syntax error if you have an if that does not have both a then branch and an else branch. Also, you should try to include any errors you get in your questions. It makes it easier for us to help. — David Young
– David Young, Commented May 21, 2022 at 2:55
The code from your edit does not seem to have a parse error, but it also doesn't give the correct answer. Think about this: What happens when you call it with 1 for b? What does it do, exactly (try to think step-by-step what its doing) — David Young
– David Young, Commented May 21, 2022 at 3:16
Your code follows the equation a*b = (a+a)*(b-1), which is not true in general. Try fixing that equation, e.g. moving the +a part somewhere else. — chi
– chi, Commented May 21, 2022 at 7:41

willeM_ Van Onsem · Accepted Answer · 2022-05-21 10:21:37Z

2

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×2^b-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.

answered May 21, 2022 at 10:21

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

MackProgram Over a year ago

Thanks for your help, can you explain to me what "multiplicacao :: (Num a, Integral b) => a -> b -> a" does?

willeM_ Van Onsem Over a year ago

@MackProgram: it is the type signature: it says that the first item has a type a that is an instance of Num (so Double, Int, etc.), and the second of type b that is an Integral type (so Int, Integer, Int16, etc.), the result is of type a, so the same type as the first item.

Collectives™ on Stack Overflow

How to use recursive in Haskell

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related