понимание базовой рекурсии

Question

public static void main (String[] args)
{
    System.out.println(factorial(5));
}

public int factorial(int n)
{
    if(n <= 1){
        return 1;
    }
    else{
        return n * factorial(n - 1);
    }
}

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

Может ли кто-нибудь кратко объяснить, как это работает в том смысле, что как оно хранится? Он начинается с вычисления 5 * (5-1), затем до 4 * (4-1), затем 3 * (3-1) ..... пока не дойдет до 1, который просто вернет 1, верно? извините за то, что был настолько схематичным, мне было бы интересно узнать, как это работает точно

спасибо

но, как это получается - он получает значения для отдельных этапов

5 * (5-1) 4 * (4-1) ... ... ...

как они сохраняются и затем возвращаются или я что-то упустил?

Answer 1

Представьте, что вы - компьютер, и кто-то вручает вам бумагу с

factorial(3)

написано на нем. Затем вы выполняете процедуру, глядя на аргумент. Поскольку это> 1, вы пишете

factorial(2) 

на другом листе бумаги и "вручите его себе", ожидая, пока вы не получите ответ на него, прежде чем продолжить.

Снова вы выполняете процедуру. Поскольку 2 все еще> 1, вы пишете

factorial(1)

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

Опять вы выполняете процедуру. На этот раз вход равен 1, поэтому вы берете первую ветвь и возвращаете 1. Вызов, который обрабатывал factorial (2), теперь имеет ответ, поэтому он умножает 2 на этот ответ (1) и возвращает. Теперь вызов, который обрабатывал factorial (3), получает свой ответ (2) и умножает его на 3, получая 6. Затем он возвращает этот ответ человеку, который начал всю операцию.

Если вы представляете, что держите листы бумаги в стопке перед собой, когда работаете, это визуализация «стопки» в памяти компьютера. Каждый рекурсивный вызов хранит параметр (и любые временные переменные) на своем собственном листе бумаги (в рамке стопки), буквально расположенном в виде стопки, как листы бумаги, одна поверх другой.

Answer 2

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

Если значение n не меньше или равно, возвращается значение n, умноженное на рекурсивный вызов factorial, но со значением n-1 до тех пор, пока не достигнет своего базового случая: 1010 * где возвращается 1

Ваш базовый случай был установлен с помощью факторного определения 0! и 1!, которые равны 1.

Может быть, эта диаграмма поможет понять, как работают звонки.

5 * fact(5-1) ->
          4 * fact(4-1) ->
                    3 * fact(3-1) ->
                              2 * fact(1) 
                                       1

Что совпадает с 5! или 5 x 4 x 3 x 2 x 1

Надеюсь, это поможет.

Answer 3

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

факториал (1) вызывается факториалом (2) вызывается факториалом (3) вызывается факториалом (4) вызывается факториалом (5)

Статья Википедии о стеках вызовов на первый взгляд кажется довольно тщательной.

Answer 4

1. При первоначальном обращении к факториалу, n = 5 и помещается в стек.
2. Тогда остальное срабатывает, поэтому 4 передается факториалу, а также толкнул в стек.
3. Тогда остальное срабатывает, так что 3 передается факториалу, а также толкнул в стек.
4. Тогда остальное срабатывает, так что 2 передается факториалу, а также толкнул в стек.
5. Тогда остальное срабатывает, поэтому 1 передается факториалу, а также положить в стек.
6. Тогда остальное срабатывает, так что 0 передается факториалу, а также положить в стек.
7. Если срабатывает if и 1 вернулся к вызывающему факториалу.
8. Если срабатывает if и 2 * 1 вернулся к вызывающему факториалу.
9. Если срабатывает if и 3 * 2 вернулся к вызывающему факториалу.
10. Если срабатывает if и 4 * 3 возвращается к вызывающему факториалу.
11. Если срабатывает if и 5 * 4 возвращается к вызывающему факториалу.

Стек также очищается, однако это слишком утомительно, чтобы печатать. По сути, все значения в вызове метода помещаются в стек и извлекаются из стека при возврате методов. Это разделяет их между рекурсивными вызовами.

Answer 5

Трудно догадаться, с какой частью рекурсии у вас возникли трудности, но я собираюсь остановиться на этой части вашего вопроса:

пока не дойдет до 1, который просто вернет 1, верно?

Я предполагаю, что вы имеете в виду, "если он просто вернет 1, почему результат функции не 1?"

Учтите, что когда вы возвращаетесь из функции (в данном случае, факториала), вы возвращаете значение тому, кто его первоначально запрашивал.

Если я скажу " дай мне factorial (5) ", то factorial (5) вернет мне значение, но прежде чем он сможет вернуть мне значение, он должен запросить factorial (4) для его значения Факториал (5) по существу говорит: « дайте мне факториал (4), чтобы я мог умножить его на 5 и вернуть его парню, который попросил факториал (5) ». Теперь factorial (4) вернет свое значение factorial (5), которое может умножить его на n и вернуть мне его значение. Напомним, что I не запрашивал значение факториала (4), мне все равно, и оно не возвращалось ко мне, оно возвращалось к факториалу (5).

К тому времени, когда вы нажмете факториал (1), у вас будут факториал (2), факториал (3), факториал (4) и факториал (5), все ожидающие ответа. Факториал (1) будет возвращать свое значение (которое равно 1, из-за вашего базового случая) факториалу (2), который в конечном итоге может вернуться к факториалу (3) и т. Д. В этот момент рекурсия завершится, и вы получить значение factorial (5) обратно.

Answer 6

Важно отметить, что «рекурсия» работает по-разному в Java (процедурный язык), чем в, скажем, Haskell или F # (функциональные языки).

В Java, когда мы вызываем рекурсию, мы делаем это, оценивая дерево выражений и разрешая каждую его часть, пока не определим значение каждой части выражения. Если нам нужно вызвать другую функцию, мы помещаем заполнитель для всех промежуточных значений в этой точке, а затем начинаем строить новое дерево выражений для новой функции.

В случае рекурсии мы выполняем вызов одной и той же функции, возможно, с различными завершающими значениями, которые необходимо решить, прежде чем мы сможем завершить оценку текущего выражения. Эти расширения неоднократно объединяются в цепочки, пока не произойдет одно из двух: 1) Мы достигаем завершающего выражения, которое возвращает управление вызывающей стороне (первая часть вашего if в этом случае), или мы исчерпываем нашу способность помещать промежуточные значения в хранилище, и мы вернуть исключение (переполнение стека).

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

Ответ Джима - отличная физическая метафора для этого.

Answer 7

.... затем 3 * (3-1) ..... пока не дойдет до 1, который просто вернет 1, верно?

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

Answer 8

Практический подход, который требует хорошей IDE (Eclipse, NetBeans, IntelliJ):

Добавьте точку останова в строку, которая читает return 1, и отладьте приложение. Когда он остановится, посмотрите на трассировку стека. Вы увидите, что метод факториала вызывался несколько раз.

Представление eclipse Debug показывает приостановленный поток и стек с шестью записями, каждая строка представляет строку кода, где вызывается другой метод (кроме верхней записи - это точка останова). factorial появляется пять раз, вы можете выбрать каждую строку и увидеть значение n в представлении Variable (это основное и должно работать на другой IDE аналогично).

Это должно дать еще одно представление о том, как работают рекурсивные вызовы методов (и почему вы получаете сообщение об ошибке нехватки памяти, если не определяете критерии выхода должным образом;))