两个非负整数相乘的递归方法

Question

刚刚在过去的考试试卷中看到了这一点，我正在寻找最好的方法，因为我无法弄清楚。我们的答案中不允许使用乘法，必须使用重复的加法。它也必须是递归的而不是迭代的。

public static int add(int a, int b) {



}

谁能帮我解决这个问题吗？ 多谢。

Answer 1

public static int add(int a, int b) {
    return a == 0 ? 0 : (add(a-1, b) + b);
}

Answer 2

如果允许轮班和改装，这里有一个有趣的。

public static int add(int a, int b) {
    return a == 0 ? 0 : add(a >> 1, b << 1) + (a % 2 == 1 ? b : 0);
}

或（用 & 代替 mod）：

public static int add(int a, int b) {
    return a == 0 ? 0 : add(a >> 1, b << 1) + (a & 1 == 1 ? b : 0);
}

Answer 3

cidermonkey 编写的是古埃及乘法的实现，并且至少在 3700 年前就已被使用。

例如，要乘以 27 * 37，请写入两个数字，然后重复将第一个数字减半并将第二个数字加倍：

27   37
13   74
 6  148
 3  296
 1  592

然后，将第二列中第一列中具有奇数的数字相加：

37 + 74 + 296 + 592 = 999

该方法今天仍然有效。数学就是这样好。