Рекурсия в Java Как это работает?

Question

Пожалуйста, объясните работу оператора рекурсии в следующем коде.

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1) * n; 
    return result; 
} 

Я понимаю, что:

В приведенном выше заявлении метод factR(n-1) не называет себя до конца. Предположим, мы хотим получить факториал из 6, который будет отправлен на этот метод в качестве аргумента. Он будет принят как параметр n, и тогда будет проверено значение n; если оно равно 1, то 1 будет возвращено. Но если это не 1, как в нашем случае, когда оно равно 6, то будет выполняться инструкция рекурсии.

Теперь проблема, с которой я сталкиваюсь, заключается в том, что первый раз n-1 становится 5 и умножается на n, что содержит значение 6, тогда оно становится 30. Теперь, где будет 30 GO?

Тогда метод будет называть себя и на этот раз n-1 становится 4, а затем умножается на n, который IF имеет значение «6», а затем 4 * 6 = 24, которое, я думаю, неверно. Потому что если мы пройдем через этот путь, то в следующем вызове процесс будет чем-то вроде: n-1 станет 3 * n, который IF имеет то же значение, то есть 6, тогда он станет 3 * 6 = 18. Затем произойдет следующий вызов и n-1 становится равным 2, если мы умножим и предположим, что n имеет значение 6, затем 2 * 6 = 12, и при последнем вызове n-1 = 1 * n = 6. Моя точка зрения заключается в том, что ясно, что n-1 уменьшит значение n-1, т.е. 6-1 = 5, затем 5-1 = 4, затем 4-1 = 3, затем 3-1 = 2 и 2-1 = 1. НО вопрос в том, что будет значением n, которое будет умножаться каждый раз, когда метод называет себя?

Если вы говорите, что когда происходит первое умножение, т.е. «n-1» становится 5, то умножается на 6 = 30 и что 30 сохраняется в «n», а затем в следующем вызове 5-1 = 4 * 30 = 120 , затем 4-1 = 3 * 120 = 360, затем 3-1 = 2 * 360 = 720 и, наконец, 1 * 720 = 720, то как Java определяет, чтобы вернуть полученное значение обратно в переменную n?

Если я помещаю еще одно заявление, чтобы проверить, что значение переменной result каждый раз, когда метод называют себя таким образом, как это:

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1)*n ; 
    System.out.println(result); 
    return result; 
} 

Тогда я получаю этот выход:

2 
6 
24 
120 
720 
Factorial of 6 is 720 

Я не понимаю, как он производит 2 в своем первом вызове. Откуда взялось значение 2, а затем 6, 24, 120 и 720? Я думаю, что я сильно застрял в работе с кодом.

Answer 1

Метод должен действительно быть структурированы так, чтобы найти факториал n:

int factorial(int n) 
{ 
    if (n == 1) 
     return 1; 

    return n * factorial(n - 1); 
} 

Это не очень хорошая идея, на мой взгляд, чтобы создать экземпляр новых переменных внутри рекурсивной функции, потому что они просто сбрасывается с каждым вызовом из-за объема.

Answer 2

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

В результате ваша функция сначала получает копию 6 и дает ее уменьшенную на 1 в качестве копии для следующего вызова вашей функции. Этот вызов получает «копию» 6-1=5 и снова уменьшает его - и так далее. Когда он достигает 1, он также возвращает 1. Затем он снова запускается через стек вызовов и умножает результат последнего вызова с локальной переменной в этом вызове. Таким образом, 1 умножается на 2 и возвращается. Этот результат умножается на 3 и так далее. Наконец, вы получаете факториал.

Answer 3

Функция расширяется до тех пор, пока не будет достигнута заявка о завершении (n == 1). Предположим, n = 6, тогда у нас есть factR(n-1) * n = factR(5) * 6, но что такое factR(5)? Ну это просто factR(4) * 5, и поэтому мы видим, что factR(5) * 6 = (factR(4) * 5) * 6. Теперь заметим, что factR(1) = 1, и мы получаем

factR(6) = factR(5) * 6 
     = (factR(4) * 5) * 6 
     = ((factR(3) * 4) * 5) * 6 
     = (((factR(2) * 3) * 4) * 5) * 6 
     = ((((factR(1) * 2) * 3) * 4) * 5) * 6 
     = ((((1 * 2) * 3) * 4) * 5) * 6 
     = (((2 * 3) * 4) * 5) * 6 
     = ((6 * 4) * 5) * 6 
     = (24 * 5) * 6 
     = 120 * 6 
     = 720 

Answer 4

В Java, у нас есть нечто, называемое стек.

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

________ 
|factR(1)| = <prints nothing> 
________ 
|factR(2)| = 2 
________ 
|factR(3)| = 6 
________ 
|factR(4)| = 24 
________ 
|factR(5)| = 120 
________ 
|factR(6)| = 720 

В основном это означает, что для метода factR(6) для завершения, factR(5) необходимо заполнить, для factR(5), чтобы закончить, factR(4) должны заполнить и так далее.

В factR(6) вы звоните factR(5), а затем дождитесь его завершения, потому что результат зависит от него.

Но, в factR(5), вы тоже делаете рекурсивный звонок, и вам нужно подождать.

И так далее, пока мы не попали в пределе factR(1), который будет просто возвращать 1.

С factR(1) завершением factR(2) можно затем распечатать результат и возвращает результат своего родительского метода, и так далее, пока factR(6) распечатывает и возвращает результаты