Факторіал у 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.

Рішення зі 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