Как рекурсивная функция оценивается в Java?

Question

Я новичок в Java, следующий код вычисляет a ^ b, я скомпилировал его на компьютере, и он работает нормально.Но я не понимаю, как это работает?Как Java-компилятор вычисляет a * power(a, b - 1) Может кто-нибудь объяснить мне этот код?

int power(int a, int b) {
    if (b < 0) {
        return 0;
    } else if (b == 0) {
        return 1;
    } else {
        return a * power(a, b - 1);
    }
}

Answer 1

Ваша функция рекурсивная.Вероятно, проще всего продемонстрировать, как это работает, на примере.

Допустим, вы хотите вычислить 2 ^ 4.Поэтому вы звоните power(2, 4);

Вот как это будет оцениваться (обратите внимание, что вы ошиблись в базовом случае):

power(2, 4) // b > 0, so it expands.
2 * power(2, 3)
2 * (2 * power(2, 2))
2 * (2 * (2 * power(2, 1)))
2 * (2 * (2 * (2 * power(2, 0)))) // Now, b == 0, so it evaluates to -1 
2 * (2 * (2 * (2 * -1)))
2 * (2 * (2 * -2))
2 * (2 * -4)
2 * -8
-16

Answer 2

Она называется рекурсивной функцией, это функция, которая сама вызывает.Чтобы убедиться, что он не вызывает себя бесконечно (и вызывает переполнение стека ;)), убедитесь, что у него есть хотя бы одно условие выхода.

Условие выхода - это одно возвращение, которое невызовите саму функцию.

Возьмите этот пример: 3^4.На самом деле 3^4 - это то же самое, что (3*3)*(4-1) или (3*3*3)*(4-2) или (3*3*3*3)*(4-3).Это именно то, что вы делаете с рекурсией!

В вашем случае вызов recusrive

return a * power(a, b - 1);

(это именно то, что я показал выше)

А выесть 2 условия выхода:

    if (b < 0) {
        return 0;
    } else if (b == 0) {
        return -1;
    } 

Answer 3

Это рекурсия.Это когда программа вызывает себя.Если вы поместите операторы печати, как показано, вы увидите, как это работает.

   static int power(int a, int b) {
      if (b < 0) {
         return 0;
      }
      else if (b == 0) {
         return 1;
      }
      else {

         System.out.println("Before: a = " + a + ", b = " + b);
         int res = a * power(a, b - 1);
         System.out.println(
               "After: res = " + res + ", a = " + a + ", b = " + b);
         return res;
      }
   }

Каждый раз, когда значения меняются, как показано призывом к власти, b уменьшается на 1. Затем, когда b == 0,программа начинает возвращать "retrieving" каждое значение из стека вызовов для выполнения вычислений.

Answer 4

Код, как указано, дает неправильные ответы;строка 5 должна читать return 1;, а не return -1;.

Java вычисляет вызов метода power, вызывая его.Здесь это ничем не отличается, это может вас немного смущать, потому что мы вызываем метод power из метода power.Что хорошо в java.

Итак, давайте попробуем power(3, 4) в качестве примера.

Java сначала проверит, если это 4 ниже 0. Это не так, пропустите это.Тогда, если это 0. Это не так, так что пропустите.Затем он вернет результат выражения (заполнив значения переменной): return 3 * power(3, 4 - 1).Чтобы вычислить это, сначала нужно вычислить power(3, 3).

Так что Java ... делает это.Он запоминает свою половину проделанной работы над power(3, 4) (он делает это «в стеке») и теперь начинает вычислять power(3, 3).Ответ - оценить return 3 * power(3, 2).Итак, Java запоминает половину работы, проделанной для power(3, 3), и идет на ее вычисление.Ответ - результат return 3 * power(3,1).Вы уже догадались, вспомните нашу работу и снова вызовите power: return 3 * power(3, 0), но, наконец, мы вышли: вызов метода power(3, 0) разрешается вторым 'if', таким образом, происходит return 1;.power(3, 0) успешно завершено!Теперь power(3, 1) может завершиться, затем power(3, 2) может завершиться до конца, и 81 возвращается.

Answer 5

step 1          : call Power(2,2)
Step 2          : go to else part a=2 and call again power(2,1)
step 3          : goto else part a=2 and call again power(2,0)
step 4          : goto else if part return -1 and go back to step 3
step 5(step 3)  : calculate 2*-1 = -2;go back to step 2
step 6(step 2)  : calculate 2*-2=-4 and finally return -4 

здесь шаги с 2 по 4 вызов одного и того же метода до совпадения с конкретным условием. это вызов рекурсии

в вашей функции есть какая-то ошибка, поэтому она возвращает 2^2= -4

Answer 6

Этот код работает на рекурсии. Каждый рекурсивный вызов помещает новый кадр стека, а затем возвращает его, когда возвращается.

Вам необходимо проверить базовый вариант в приведенном выше коде. Таким образом, когда b == 0, он должен вернуть 1.