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

Сегодня мы поговорим о факториалах. Это одна из самых базовых функций, которые программисту нужно знать, а заодно уметь с этим работать. Итак, приступим. Факториал числа n это значение произведения (умножения) всех натуральных чисел от 1 до n, которое обозначается как n! В Java факториал считают тремя способами: обычным циклом, рекурсией и через Stream API. Главный подводный камень не в алгоритме, а в типе результата: int хватает только до 12!, long до 20!, а дальше нужен BigInteger, иначе число молча переполнится. Ниже все три способа показаны сначала на int, потом на BigInteger.

Кратко

• Факториал n это произведение всех натуральных чисел от 1 до n, обозначается n!. По договоренности 0! = 1.
• В Java его считают тремя способами: циклом for, рекурсией и через IntStream.rangeClosed(2, n).reduce(...). Результат одинаковый, отличается только запись.
• int вмещает факториал только до 12!, long до 20!. Дальше результат молча переполняется: ни ошибки, ни предупреждения, просто неверное число.
• Для больших n нужен BigInteger: предела у него нет, кроме памяти, а 100! это число из 158 цифр.
• У рекурсивного варианта обязательно условие выхода (f <= 1). Без него метод будет вызывать сам себя, пока не кончится стек, и упадет с StackOverflowError.
• Чтобы переполнение int не проходило молча, умножайте через Math.multiplyExact: при выходе за пределы типа он бросит ArithmeticException вместо мусора.

Как считается факториал

Как это выглядит:

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

Три способа посчитать факториал на int

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

Обычное решение: цикл

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

Ничего сложного: используем пришедшее число как размер нашего цикла, в котором умножаем на все предыдущие числа, пока не дойдем до f. Проверки на отрицательное число здесь нет, и это касается всех листингов ниже: для отрицательного f цикл в тело не зайдет и вернет 1, рекурсия сработает так же из-за условия f <= 1. Факториал отрицательных чисел не определен, поэтому в рабочем коде первой строкой метода стоит поставить if (f < 0) throw new IllegalArgumentException("Факториал отрицательного числа не определен");. В статье эта строка опущена ради краткости. Еще одна оговорка. При большом f произведение перестанет помещаться в int, и умножение молча вернет неверное число. Если хочется, чтобы переполнение сразу бросалось в глаза, умножайте через Math.multiplyExact(result, i): при выходе за пределы int он бросит ArithmeticException. У класса Math есть такие же безопасные версии для сложения и вычитания. Ниже мы решим ту же проблему иначе, через BigInteger. И в 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, а именно показываем в нем, как мы хотим их объединить. Он возвращает не число, а обертку OptionalInt, и результат мы достаем из нее методом getAsInt.

Применение BigInteger

В Java часто для обработки чисел, особенно БОЛЬШИХ, используется класс BigInteger. Ведь если мы используем int, то без потери данных получится посчитать только 12!: уже 13! равен 6 227 020 800, а это больше максимума int, который равен 2 147 483 647. У long запас побольше, но и он заканчивается на 20!: 21! в 9 223 372 036 854 775 807 не влезает. Причем ошибки вы не увидите: цикл на int для 13 вернет 1 932 053 504, а для 17 и вовсе отрицательное число. А что если нам нужен будет факториал 100? Давайте же рассмотрим предыдущие варианты решения, но с использованием BigInteger.

Обычное решение с 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 для умножения предыдущего значения факториала на текущее число.

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

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

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

Решение со Stream и BigInteger

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

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

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

На этом все. Если коротко подытожить: цикл это выбор для рабочего кода, он быстрее всех и не тратит стек; рекурсия хороша, чтобы понять саму идею рекурсии, но на большом n упрется в глубину стека; Stream уместен там, где вокруг и так все написано на стримах. А тип результата выбирайте не по привычке, а по размеру числа: до 12! хватит int, до 20! хватит long, дальше только BigInteger.

Вопросы и ответы

Что такое факториал и чему равен факториал нуля?

Факториал числа n это произведение всех натуральных чисел от 1 до n, записывается n!. Например, 5! = 1 * 2 * 3 * 4 * 5 = 120. Факториал нуля по договоренности равен единице: 0! = 1. Это не исключение ради красоты, а условие, при котором формулы комбинаторики работают без особых случаев.

Как посчитать факториал в Java без рекурсии?

Обычным циклом: завести переменную result = 1 и в цикле от 1 до n умножать ее на счетчик. Это самый простой и самый быстрый способ, и для него не нужно ничего, кроме for. Второй вариант без рекурсии это Stream API: IntStream.rangeClosed(2, n).reduce((x, y) -> x * y).getAsInt().

До какого числа факториал помещается в int и long?

В int помещается 12! = 479 001 600, а 13! уже нет. В long помещается 20! = 2 432 902 008 176 640 000, а 21! уже нет. Все, что больше, считают через BigInteger.

Почему факториал большого числа в int получается неверным?

Потому что int переполняется молча. Когда произведение выходит за 2 147 483 647, старшие биты просто отбрасываются, и вместо ошибки вы получаете другое число: 13! в int дает 1 932 053 504, а 17! уже отрицательное. Если такое поведение недопустимо, умножайте через Math.multiplyExact, он бросит ArithmeticException, или сразу берите BigInteger.

Как посчитать факториал 100 в Java?

Только через BigInteger. Стартуем с BigInteger.ONE и в цикле умножаем через multiply(BigInteger.valueOf(i)), либо в один вызов: IntStream.rangeClosed(2, 100).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get(). Результат это число из 158 цифр, и ни в один примитивный тип оно не поместится.

Какой способ лучше: цикл, рекурсия или Stream?

Для реального кода цикл: он быстрее всех и не тратит стек. Рекурсия хороша как учебный пример, но для большого n она упрется в глубину стека и бросит StackOverflowError. Stream читается компактно и уместен там, где вокруг и так все написано на стримах. Правильность результата у всех трех одинаковая, разница только в читаемости и ресурсах.

Читайте также

• Что должен знать программист на Java о числах Фибоначчи
• BigInteger и BigDecimal
• Цикл for в Java
• Лямбда-выражения в Java. Часть 1