c++ - 使用递归函数C++进行乘法

Question

我做了一个递归函数来计算x * y，其中x和y都是整数(x和y> = 0)。我的公式是:
x * y =

0 ，如果x等于0

(x >> 1)*(y << 1)，如果x是偶数

(x >> 1)*(y << 1)+ y 如果x是奇数

“<<”和“>>”是左移和右移按位运算符。这是我的代码:

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);
    }
}

上面的递归函数应该返回(x * y)值，但是当我测试时它们都是错误的，我也不知道为什么。我做错什么了？我怎样才能解决这个问题？

Answer 1

您的问题是x % 3，如果x = 5会怎样？你跳过它。这是代码的改进版本。

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);
}

甚至这个:

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;
}

这是安迪建议的超快速版本:

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;
}

作为速度的挑战，这是非递归版本:

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; 
}

注意:我知道这个问题与递归方法有关，但正如我编写非递归算法的挑战一样。