Изучение Java рекурсии из книги, Java, полный справочник

Question

Изучение рекурсии и проблемы с кодом, приведенным ниже, в строке 6,

int result=fact(n-1)*n;

Когда я удаляю «факт», программа работает так, как я думаю, и печатает:

Factor of 3 6
Factor of 4 12
Factor of 5 20

а с "фактом" в нем выдает вывод ниже? Что делает эта линия, и что такое «факт»? Спасибо всем.

Factor of 3 6
Factor of 4 24
Factor of 5 120

Answer 1

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

Например, факториал 5 рассчитывается следующим образом:

5! = 5 * 4 * 3 * 2 * 1

Кроме того, есть еще один способ думать об этом:

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1

Как пишется вторая серия равенств, видно, что факториал может быть вычислен рекурсивным способом. Например:

5! = 5 * 4! --> 5! = 5 * (4 * 3!) --> 5! = 5 * (4 * (3 * 2!)) --> and so on.

Функция fact в вопросе выполняет факториальную функцию, как написано во второй серии равенств:

fact(n) = n * fact(n-1);

Итак, когда вызывается метод fact, способ его вызова можно представить как что-то вроде следующего:

fact(5) --> fact(5 * fact(4)) --> fact(5 * fact(4 * fact(3))) --> and so on.

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

Answer 2

Очевидно, что это классический пример рекурсии с использованием вычисления factorial .

То, что вы называете fact(N), обычно обозначается буквой N! (в любом случае математиками)

п! = n x (n-1) x (n-2) ...

так 5! = 5 x 4 x 2 x 1 = 120
4! = 4 x 3 x 2 x 1 = 24

Кстати, это может быть немного нелогичным, но 0! определяется как 1

Answer 3

Когда вы снова удаляете вызов факту, вы просто делаете:

println(n * (n-1))

Вы можете попробовать сделать факториал с помощью только цикла и посмотреть, насколько отличается код.

Рекурсия может быть полезна, но вы будете ограничены в величине (n), которую вы можете вызвать, так как в конечном итоге вы переполните стек, поскольку вычисления не будут выполняться, пока вы не достигнете условия, отмечающего конец рекурсия.

Чтобы лучше понять рекурсию, вы можете посмотреть по этой ссылке: http://en.wikipedia.org/wiki/Recursion_(computer_science)

Answer 4

</p> <pre><code>fact(5) = fact(4) * 5 fact(4) = fact(3) * 4 fact(3) = fact(2) * 3 fact(2) = fact(1) * 2 fact(1) = 1 fact(5) = fact(4) * 5 = fact(3) * 4 * 5 = .. = 1 * 2 * 3 * 4 * 5 = 120

Функция рекурсивно вызывает сама себя, поэтому вычисление оборачивается в 1 * 2 * 3 * 4 * 5.