Multiplying using recursive function C++

Question

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 =

• 0, if x is equal 0
• (x >> 1)*(y << 1), if x is an even number
• (x >> 1)*(y << 1) + y, if x is an odd number

"<<" 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?

Answer 1

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.