Функция факториала

Для некоторых задач может быть естественным определить задачу с точки зрения самой задачи.

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

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

Давайте рассмотрим другой пример, который мы видели раньше.

Мы ввели функцию факториала, когда мы обсуждали циклы.

Напомним, что факториал целого числа n представляет собой последовательное умножение чисел от n до 1.

Например, при вычислении 6!, результат будет умножение 6, 5, 4, 3, 2, 1, который даст 720.

Также легко видеть, что 6! можно переписать в виде 6 умножить на 5!, где 5! равен оставшейся части умножений, следующих за 6. Так что мы выражаем 6! как 5!, который является упрощенной задачей, по сравнению с 6!.

Таким образом, в целом, мы можем выразить функцию факториала как n! = n * (n-1)!.

Здесь n! может быть получен путем вычисления n-1 факториал.

Вы решили полностью задачу? Почти.

У нас еще есть вычисление n-1!. Как мы вычисляем n-1!?

Мы можем получить n-1!, вычисляя n-2!.

Но это, кажется никогда не заканчивающейся последовательностью, если нет какого-то завершающего состояния.

В случае факториала, мы знаем, что он определяется только для неотрицательных чисел.

И мы также знаем, что 1! или 0! дает значение 1.

Давайте игнорировать 0! в нашем обсуждении, и n-1! продолжает уменьшаться до тех пор, пока n-1 не станет равен 1, и мы можем остановить повторный вызов функции факториала.

Это часто называют базовым состоянием.

Чтобы написать это в явном виде, когда n равно 1, мы должны получить n! равен 1, в противном случае, n! равно n * n-1!.

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

В Java можно определить рекурсивную функцию.

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

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

В 70-х годах, термин фрактал был введен для визуализации самоподобных шаблонов, используя компьютерное моделирование.

Мы обсудим некоторые из них позже.

Давайте теперь постараемся реализовать вычисление n! рекурсивным образом.

Здесь мы объявляем метод с именем fact, который возвращает целое значение.

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

Метод возьмет целый параметр n, для которого мы вычислим факториал.

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

То есть, n! равен 1, если n меньше или равно 1, при условии, что n является неотрицательным.

В противном случае, то есть, когда n больше, чем 1, n! будет n * n-1!.

Обратите внимание, что мы вызываем метод внутри определения метода, и это то, что мы раньше не видели.

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

Давайте более внимательно посмотрим на то, как рекурсивный вызов метода фактически работает в Java.

Возьмем простой случай, когда n равно 3.

Это функция факториала, которую мы только что определили.

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

То есть, будет вычисляться fact(3), который равен 3 умножить на fact (n-1), с n равным 3, то есть, метод будет вызываться с параметром 2 или 3-1.

В этом месте мы не знаем пока результат для fact(2).

Поэтому, прежде чем мы можем перемножить fact(2) на 3, мы должны сначала выяснить значение fact(2).

Далее, мы должны сделать рекурсивный вызов метода с 2 в качестве параметра.

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

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

Так что n в fact(2) будет иметь значение 2 и условие n меньше чем или равно 1 снова дает ложь. Поэтому будет выполнен код else.

То есть, два умножить на fact(n-1) или 1 при n, равным 2.

В этот момент, значение для fact(1) еще не определено.

Далее, производится рекурсивный вызов метода с 1 в качестве параметра.

В этом случае, с n, равным 1, if условие становится верным, и 1 будет возвращена в качестве результата для fact(1).

После того, как значение для fact(1) определяется, мы можем вернуться к вычислению fact(2) путем умножения 2 на fact(1), который только что получили как возвращенное значение 1.

Таким образом fact(2) может быть вычислен путем умножения 2 на 1 и получим 2 как возвращенный результат для fact(2).

Используя значение для fact(2), мы можем снова вернуться к вычислению fact(3) путем умножения 3 на fact(2) или 2 и получить значение 6.

Таким образом, мы имеем возвращаемое значение для fact(3), который является конечным результатом, который мы хотим получить для 3!.

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

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

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

Помните, что, когда мы обсуждали структуру цикла, используя факториал как пример, мы реализовали факториал с использованием различных видов циклов, а именно, while, do-while и for цикла.

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

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

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

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

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

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

Давайте вернемся к задаче рукопожатия.

Напомним, что общее количество рукопожатий для n человек, это h(n) = h(n-1) + (n-1).

То есть, h(n) вычисляется с помощью h(n-1).

Поскольку h определен в терминах h меньшего n, это может быть реализовано с использованием рекурсивного метода.

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

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

Код else рекурсивного вызова обеспечивает случаи для n больше, чем 2.

Как альтернатива, это также может быть реализовано с помощью цикла.

На самом деле, здесь мы можем переформулировать решение как сумму целых чисел от 1 до n-1 = n(n-1) / 2.

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

Откроем IDEA и посмотрим на работающую задачу рукопожатий.

Здесь мы реализовали программу рукопожатий, как обсуждали перед этим.

Скомпилируем и запустим эту программу.

Попытаемся запустить программу, вводя различные значения n.

Если мы введем 3 в качестве значения n, вы увидите, что 3 является общим количеством рукопожатий.

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

Давайте сделаем еще один запуск, введя 5.

Теперь у вас есть 5 человек в комнате.

И вы можете видеть, что возвращаемый результат 10 здесь равен 6 плюс 5 минус 1, что есть 4.

Так что у вас есть 6 плюс 4 равно 10.