Факториал в Java-программировании

Сегодня мы поговорим о факториалах. Это одна из самых базовых функций, которые программисту нужно знать, а заодно — уметь с этим работать. Итак, приступим. Факториал числа n — это значение произведения (умножения) всех натуральных чисел от 1 до n, которое обозначается как n! Как это выглядит:

1! =  1
2! =  1 * 2 = 2
3! =  1 * 2 * 3 = 6
4! =  1 * 2 * 3 * 4 = 24
5! =  1 * 2 * 3 * 4 * 5  = 120

И ещё одно небольшое правило, для 0:

!0  = 1

Если мы хотим, к примеру, получить разницу факториалов 6! и 4!:

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696

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

Обычное решение

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}

Ничего сложного: используем пришедшее число как размер нашего цикла, в котором умножаем на все предыдущие числа, пока не дойдём до f. И в main:

System.out.println(getFactorial(6) - getFactorial(4));

Проверяем и получаем искомый результат: 696.

Рекурсивное решение

Рекурсия — это выполнения некоторой логики путем вызова методом самого себя. Такой метод называют рекурсивным. Как правило он состоит из двух частей:

1. условие выхода из метода, при достижении которого метод должен перестать вызывать самого себя и начать отдавать значения наверх. Ведь иначе мы получим бесконечный цикл из вызова методом самого себя и как следствие — StackOverflowError.

2. некоторая обработка (логика), необходимая в данной ситуации + вызов самого себя, но уже с другим входящим значением.

Идеальным примером для рекурсии у нас сегодня и послужит нахождение факториала:

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

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

Решение со Stream

Для не знающих stream функционал или для желающих освежить его в памяти, будет полезно прочитать вот это.

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

Тут мы используем специальный класс IntStream , дающий дополнительные возможности при работе со stream из int значений. Для создания такого stream мы используем его статический метод rangeClosed, который создаёт значения с 2 до f включительно с шагом 1. Далее мы объединяем все значения с помощью метода reduce, а именно — показываем в нем, как мы хотим их объединить. Наконец, мы получаем результирующее значение с помощью терминального метода getAsInt.

Применение BigInteger

В Java часто для обработки чисел, особенно БОЛЬШИХ, используется класс BigInteger. Ведь если мы используем int, то максимальный факториал, который мы можем взять без потери данных, — 31, для long — 39. А что если нам нужен будет факториал 100? Давайте же рассмотрим предыдущие варианты решения, но с использованием BigInteger.

Обычное решение

public static BigInteger getFactorial(int f) {
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

Алгоритм подсчёта по сути тот же, но здесь мы используем возможности BigInteger: BigInteger.ONE — для задания стартового значения 1. multiply — умножение между предыдущим значением факториала и текущим числом.

Рекурсивное решение

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

Общая логика решения не изменяется, разве что добавляются некоторые методы для работы с BigInteger.

Решение cо Stream

public static BigInteger getFactorial(int f) {
  if (f < 2) {
     return BigInteger.valueOf(1);
  }
  else {
     return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
  }
}

По сути всё то же самое, но с BigInteger. В stream у нас появился метод mapToObj, которым мы преобразуем значения int в BigInteger, чтобы в дальнейшем перемножить их между собой с помощью multiply (ну и добавился get для взятия объекта из обёртки Optional). Если же мы запустим любой из этих трёх методов с аргументом 100, то у нас не случится переполнения и мы получим:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000