CODEWITHSUNDEEP
c++functionrecursionmultiplication
Halsey
Halsey

Reputation: 129

Multiplying using recursive function C++

I did a recursive function to calculate x*y with x and y are all integers (x and y >= 0). My formula is: x * y =

"<<" and ">>" are Left Shift and Right Shift Bitwise Operator. Here is my code:

int multiply(int x, int y) {
    int y1 = 0;
    if (x == 0) return 0;
    else if (x % 3 == 0) {
        y1 = y;
        x = x >> 1;
        y = y << 1;
        return (multiply(x, y) + y1);
    }
    else if (x % 2 == 0) {
        x = x >> 1;
        y = y << 1;
        return multiply(x, y);
    }
}

The recursive function above is supposed to return (x*y) value but they were all wrong when i tested and i don't know why. What did i do wrong? How can i fix this?

Upvotes: 0

Views: 873

Answers (4)

ofderdiyok
ofderdiyok

Reputation: 11

Recursive function related to multiplication of natural numbers:

int multCool(int a, int b)
{
    return (b==1 ? a: a+ multCool(a,b-1));
}

Upvotes: 0

user5550963
user5550963

Reputation:

Your problem is wit x % 3, what happens if x = 5? you skip it. Here is improved version of your code.

int multiply(int x, int y) {
    if (x == 0)
        return 0;
    else if (x % 2 == 1)
        return (multiply(x >> 1, y << 1) + y);

    return multiply(x >> 1, y << 1);
}

or maybe even this:

int multiply(int x, int y) {
    if (x == 0)
        return 0;
    int m = multiply(x >> 1, y << 1);

    if (x % 2 == 1)
        m += y;

    return m;
}

Here is super fast version suggested by Andy:

int multiply(int x, int y) {
    if (x == 0)
        return 0;
    int m = multiply(x >> 1, y << 1);

    if (x & 1)
        m += y;

    return m;
}

As a challenge of speed, here is non recursive version:

int multiply (int x, int y) {
    int y1 = 0;
    for (; x > 0; x = (x >> 1), y = (y << 1)) 
        if (x&1) 
            y1 += y;

    return y1; 
}

NOTE: I know this question is about recursive method but just as a challenge I wrote non-recursive algorithm.

Upvotes: 3

Aftab22
Aftab22

Reputation: 550

This is what i feel is the simplest approach to carry out recursive multiplication. Do let me know if its efficient enough for you.

#include<iostream>
using namespace std;
 
float multiply(float a, float b) {
 
    //no zeros bro
    if (b == 0)
        return 0;
 
    //let the recursion begin
    if (b > 0)
        return x + multiply(a, b - 1);
 
    //negatives stay away pliz
    if (y < 0)
        return -multiply(a, -b);
}
 
int main() {
    float a, b, result;
    cout << "Enter the two numbers";
    cin >> a >> b;
 
    result = multiply(a, b);
 
    //And the result is.................
    cout << result;
    return 0;
}

Upvotes: 0

cigien
cigien

Reputation: 60218

You are not checking if x is odd correctly here:

else if (x % 3 == 0) {  // e.g. fails on x = 1

Instead, you need to do

else if (x % 2 == 1) {

Here's a demo.

Note that this makes the following else check for even values of x redundant:

else if (x % 2 == 0) {  // can just be an unconditional else

Also, since you are returning from the x == 0, and x % 2 == 1 branches, the else conditions can be removed as well. You can also factor out the repeated code to make the function simpler, like this:

int multiply(int x, int y) {
    if (x == 0) return 0;
    if (x % 2 == 1) 
        return (multiply(x >> 1, y << 1) + y);
    else 
        return multiply(x >> 1, y << 1); 
}

Here's a demo.

Upvotes: 1

Related Questions