使用递归函数 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);
    }
}

上面的递归函数应该是return(x*y)的值，但是我测试的时候都错了，我也不知道为什么。我做错了什么？我该如何解决这个问题？

Answer 1

您在这里没有检查 x 是否正确：

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

相反，您需要做

else if (x % 2 == 1) {

这是一个 demo。

请注意，这使得以下 else 检查 x 的偶数变得多余：

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

此外，由于您是从 x == 0 和 x % 2 == 1 分支返回的，因此 else 条件也可以删除。也可以把重复的代码分解出来，让函数更简单，像这样：

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

这里是 demo。

Answer 2

你的问题是 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; 
}

注意：我知道这个问题是关于递归方法的，但作为一个挑战，我写了非递归算法。

Answer 3

这是我觉得最简单的递归乘法。如果它对你足够有效，请告诉我。

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

Answer 4

自然数乘法相关的递归函数：

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

使用递归函数 C++ 相乘

Multiplying using recursive function C++

c++

recursion

function

multiplication