Factorial in Java programming

Today we will talk about factorials. This is one of the most basic functions that a programmer needs to know, and at the same time be able to work with it. So let's get started. The factorial of n is the value of the product (multiplication) of all natural numbers from 1 to n, which is denoted as n! What it looks like:

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

And one more small rule, for 0:

!0  = 1

If we want, for example, to get the factorial difference 6! and 4!:

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

Let's take a look at what this would look like in Java and understand several ways in which factorial can be calculated.

The usual solution

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

Nothing complicated: we use the received number as the size of our cycle, in which we multiply by all previous numbers until we reach f. And in main:

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

We check and get the desired result: 696.

Recursive solution

Recursion is doing some logic by calling a method on itself. This method is called recursive. Typically it consists of two parts:

1. method exit condition, upon reaching which the method should stop calling itself and start passing values ​​up. Otherwise, we will get an infinite loop from calling a method on itself and, as a result, a StackOverflowError .

2. some processing (logic) necessary in a given situation + calling itself, but with a different incoming value.

Our ideal example for recursion today is finding the factorial:

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

We set the condition for exiting the recursion when it reaches 1. If the argument is not 1, then we multiply the current value by the result of the next call to this method (where we send the current value -1).

Solution with Stream

For those who do not know the stream functionality or for those who want to refresh their memory, it will be useful to read this .

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

Here we use a special class IntStream, which provides additional capabilities when working with stream from int values. To create such a stream, we use its static method rangeClosed, which creates values ​​from 2 to f inclusive with a step of 1. Next, we combine all the values ​​using the reduce method, namely, we show in it how we want to combine them. Finally, we get the resulting value using the getAsInt terminal method.

Using BigInteger

In Java, the BigInteger class is often used to handle numbers, especially BIG ones . After all, if we use int, then the maximum factorial that we can take without losing data is 31, for long - 39. But what if we need a factorial of 100? Let's look at the previous solutions, but using BigInteger.

The usual solution

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;
}

The counting algorithm is essentially the same, but here we use the capabilities of BigInteger: BigInteger.ONE - to set the starting value to 1. multiply - multiplication between the previous factorial value and the current number.

Recursive solution

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

The general logic of the solution does not change, except that some methods for working with BigInteger are added.

Solution with 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();
  }
}

Essentially everything is the same, but with BigInteger. In stream we now have the mapToObj method, with which we convert int values ​​to BigInteger in order to subsequently multiply them together using multiply (well, we added get to take an object from the Optional wrapper ). If we run any of these three methods with argument 100, then we will not have an overflow and we will get:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000