Recursive method to multiply two non-negative ints

Just saw this in a past exam paper and am looking for the best way to do it since I can't figure it out. We are not allowed use multiplication in our answer, it must use repeated addition. It must also be recursive and not iterative.

public st开发者_StackOverflow中文版atic int add(int a, int b) {



}

Can anyone help me figure this out please? Thanks a lot.

---

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

---

If shifts and mods are allowed, here's a fun one.

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

or (with an & instead of mod):

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

---

What cidermonkey has written is an implementation of ancient Egyptian multiplication, and was used at least 3700 years ago.

For example, to multiply 27 * 37, write the two numbers and repeated halve the first number and double the second:

27   37
13   74
 6  148
 3  296
 1  592

then, add the numbers in the second column which have a odd number in the first column:

37 + 74 + 296 + 592 = 999

The method still works today... mathematics is good like that.