Рекурсивный метод - Java

Question

Информация о добавлении:

Чип не поддерживает умножение, только добавление. Я должен обойти эту проблему, создав рекурсивный метод mult(), который выполняет умножение на x и y, добавляя x к себе y раз. Его аргументы - это x и y и его значение - произведение x и y. Затем я должен написать метод, а main() - .

Это чисто логическое мышление, но я теряюсь каждый раз, когда я пытаюсь думать, что делать.

Я застрял в математике часть .. Что у меня есть, что не работает, и я знаю, что математика это неправильно, но я не очень хорошо в этом:

public static void mult(int x, int y) { 
    x = 0; 
    y = 0; 
    if (y > 0) { 
     for (int i = 0; i < y; i++) { 
      x = x * (x * y); 
      return mult(x, y); 
     } 
    } 
} 

Answer 1

public static int mult(int x, int y) { 
     if (y == 0) { 
      return 0; 
     } 
     if (y > 0) { 
      return x + mult(x, y - 1); 
     } else { 
      return -x + mult(x, y + 1); 
     } 
    } 

это решение, кстати

Answer 2

Когда я слышу " рекурсия», я ожидаю увидеть две вещи:

1. функция называющая себя с модифицированными аргументами каждый раз.
2. A состояние остановки справа вверху, которое сообщает функции, когда останавливается, избегая бесконечного стека.

Итак, где ваши? Начните с написания слов вниз, прежде чем писать код.

Answer 3

... путем добавления x к себе y раз.

Вы могли бы это сделать, а не умножать. О, и, может быть, если вы не установите как x, так и y в ноль, вам нужно будет что-то добавить ;-)

Последнее: если вам нужно рекурсивное решение, вам не нужен цикл for ,

Answer 4

Все, что вам нужно помнить о том, что умножение повторное добавление (предполагая, что оба операнда >= 0), так что мы имеем:

• Базовый случай, когда y равен нулю
• Если y не равен нулю, а затем добавить x еще один раз, и вычесть из 1y

Обратите внимание, что до тех пор, пока y будет положительным, оно в конечном итоге будет иметь значение 0.Поэтому в основном мы продолжаем добавлять x общее количество y раз; это то, что я имею в виду:

public static int mult(int x, int y) { 
    if (y == 0) 
     return 0; 
    return x + mult(x, y-1); 
} 

тот же код может быть записан в tail-recursive стиле, тоже - это значит: нет ничего, чтобы сделать после того, как рекурсивные возвраты вызова, и это очень важно для некоторых языков, которые поддерживают SO- называется оптимизация хвостового вызова:

public static int mult(int x, int y, int accumulator) { 
    if (y == 0) 
     return accumulator; 
    return mult(x, y-1, x + accumulator); 
} 

выше будет вызван следующим образом, заметив, что последний параметр всегда инициализируется в нуль:

mult(10, 5, 0) 
=> 50 

Answer 5

J ava не имеет TCO по дизайну, поэтому использование рекурсии для линейных (не древовидных) процессов - очень плохая идея. Особенно для такой задачи, которая, скорее всего, станет узким местом в вашей программе. Вместо этого используйте цикл.

О, это должно быть рекурсивным? Похоже, домашнее задание. Сделай это сам тогда.

Answer 6

Одна из возможностей - использовать аккумулятор, который будет хранить текущее значение умножения. Я заменяю отсутствующие высказывания на ??? :

public static void main(String []args){ 
     System.out.println(mult(2,5)); 
} 
    public static int mult(int x, int y) { 
     if(???) return ???; 
     else return multAcc(???,???,???); 
    } 

    private static int multAcc(int x, int y, int acc){ 
     if(???) return ???; 
     else return multAcc(???, ???, ???); 
    }