Рекурсивный метод для умножения двух неотрицательных целых чисел

#java #recursion #multiplication

#java #рекурсия #умножение

Вопрос:

Только что видел это в прошлой экзаменационной работе и ищу лучший способ сделать это, поскольку я не могу в этом разобраться. Нам не разрешается использовать умножение в нашем ответе, оно должно использовать повторное сложение. Он также должен быть рекурсивным, а не итеративным.

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



}

Кто-нибудь может помочь мне разобраться в этом, пожалуйста?
Большое спасибо.

1. Подсказка : a b равно a 1 1 1... ( 1 повторяется b раз)

2. в названии вашего метода написано «add», а в вашей теме написано «multiply», что это?

3. Это умножение с использованием рекурсивного сложения.

Ответ №1:

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

1. @Eng. Фуад, это была спецификация. Возможно, было бы полезно сделать его более общим, но это также привело бы к риску чрезмерного усложнения для OP.

2. Извините, я не увидел «неотрицательный» в самом начале.

Ответ №2:

Если разрешены сдвиги и модификации, вот забавный.

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

или (с amp; вместо mod):

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

Ответ №3:

То, что написал cidermonkey, является реализацией древнеегипетского умножения, и использовалось по крайней мере 3700 лет назад.

Например, чтобы умножить 27 на 37, запишите два числа и повторно уменьшите первое число вдвое и удвоьте второе:

затем добавьте числа во втором столбце, которые имеют нечетное число в первом столбце:

 37   74   296   592 = 999

Метод все еще работает сегодня … математика хороша и так.