Calculate Factorial With Java - Iterative and Recursive

Introduction

Calculating a factorial of a number is a straightforward task. A factorial of a number is the product of that number (positive integer) and all positive integers less than that number. In other words - multiplying a number by all of the whole numbers from that number to 1.

0! equals 1 as well, since you can't exactly go down from 0 to 1.

It's simply an agreement that 0! is equal to 1, and a common explanation of this (sadly unattributable to a single person) is: 'Because there is exactly one way to do nothing.'

A factorial is denoted by the integer and followed by an exclamation mark.

5! denotes a factorial of five. Alternatively, you can simply say five factorial.

And to calculate that factorial, we multiply the number with every positive whole number smaller than it:

$$
5! = 5 * 4 * 3 * 2 * 1
5! = 120
$$

In this tutorial, we'll learn how to calculate a factorial of an integer in Java. This can be done using loops or recursion - though recursion is arguably a more natural approach. Of course, you should implement the one you're more comfortable with.

Calculating Factorial Using Loops

Let's start out calculating factorials using loops - while and for. We can also use do-while loops, but the initial do block doesn't do much for us here and would introduce a potential erroneous edge-case, so we'll skip it.

The general process is pretty similar for both loop types - all we need is a parameter as input and a counter to iterate over the numbers.

Let's start with the for loop:

public static int getFactorialForLoop(int n) {
    int result = 1;
    if (n > 1) {
        for (int i = 1; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
    else {
        System.out.println("n has to be positive");
        return result;
    }
}

We've actually strayed a bit away from the original definition here - we're counting from 1 to n, while the definition of factorial was from the given number down to 1.

When you put it down on paper, though, mathematically:

$$
1 * 2 * 3 * 4 ... * n = n * (n-1) * (n-2) * (n-3) * (n-4) ... * (n - (n-1))
$$

These are equal statements, and you can really either go from 1 to n, or the other way around.

To simplify, (n - (n-1)) will always be equal to 1.

That means that it doesn't matter in which direction we're iterating. It can start from 1 and increase towards the n, or it can start from n and decrease towards 1.

Why?

Well, if you turn the loop the other way around, the method doesn't get much more complicated, but it's just a little bit less clean:

public static int getFactorialForLoop(int n) {
    int result = n;
    if (n >= 1) {
        for (int i = n-1; i >= 1; i--) {
            result = result * i;
        }
        return result;
    }
    else {
        System.out.println("n has to be positive");
        return 1;
    }
}

Now that that's clarified, let's start breaking the method down.

It takes in a parameter, n, which denotes the number we're calculating a factorial for. First, we define a variable named result and assign 1 as a value to it.

Why assign 1 and not 0?

If we were to assign 0 to it then all the following multiplications would contain that 0. Naturally, it would collapse the entire operation to a huge 0.

Then we start our for loop with defining i as the counter that starts from 1. Notice that the condition statement is i <= n; in order to include the n itself as well.

Inside the for loop, we multiply the current value of result with the current value of our index i.

Finally, we return the final value of the result. In order to get input from the user, remember to import the java.util.Scanner.

If you'd like to read more about getting user input in Java - read our Guide to the Scanner class.

Let's test our method and print the results:

Scanner scanner = new Scanner(System.in);
int inp;
        
System.out.println("Enter a number: "); 
inp = Integer.parseInt(scanner.nextLine());   
           
System.out.println("The result is: " + getFactorialForLoop(inp));        

    
public static int getFactorialForLoop(int n) {
    int result = 1;
    if (n >= 1) {
        for (int i = 1; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
    else {
      System.out.println("n has to be positive");
      return result;
    }

It will prompt the user to give input. We'll try it with 4:

Enter a number: 4
The result is: 24

You can use a calculator to verify the result:

4! is 4 * 3 * 2 * 1, which results 24.

Now let's see how we can calculate factorial using the while loop. Here's our modified method:

public static int getFactorialWhileLoop(int n){
    int result = 1;
    while (n > 1) {
        result = result * n;
        n -= 1;
    }
    return result;
}

This is pretty similar to the for loop. Except that, this time we're moving from n towards the 1, closer to the mathematical definition. Let's test our method:

System.out.println("Enter a number: "); 
inp = Integer.parseInt(scanner.nextLine());   
    
System.out.println("The result is: " + getFactorialWhileLoop(inp));   

We'll enter 4 as an input once more:

Enter a number: 4
The result is: 24

Although the calculation was 4*3*2*1 the final result is the same as before.

Now let's take a look at how to calculate the factorial using a recursive method.

Calculating Factorial Using Recursion

A recursive method is a method that calls itself and terminates the call given some condition.

In general, every recursive method has two main components: a base case and a recursive step.

Base cases are the smallest instances of the problem. Also, they must have a break, a case that will return a value and will break out of the recursion. In terms of factorial methods, the base case is when we return the final element of the factorial, which is 1.

Without a base case or with an incorrect base case, your recursive method can run infinitely, causing an overflow.

Recursive steps - as the name implies, are the recursive part of the method, where the whole problem is transformed into something smaller. If the recursive step fails to shrink the problem, then again recursion can run infinitely.

Consider the recurring part of the factorials:

• 5! is 5 * 4 * 3 * 2 * 1.

But we also know that:

• 4! is 4 * 3 * 2 * 1.

In other words 5! is 5 * 4!, and 4! is 4 * 3! and so on.

So we can say that n! = n * (n-1)!. This will be the recursive step of our factorial!

A factorial recursion ends when it hits 1. This will be our base case. We will return 1 if n is 1 or less, covering the zero input.

Let's take a look at our recursive factorial method:

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

As you see the if block embodies our base case, while the else block covers the recursive step.

Let's test our method:

System.out.println("Enter a number: "); 
inp = Integer.parseInt(scanner.nextLine());   
    
System.out.println("The result is: " + getFactorialRecursively(inp)); 

We will enter 3 as input this time:

Enter a number:3
The result is: 6

We get the same result. But this time, what goes under the hood is rather interesting:

You see, when we enter the input, the method will check with the if block, and since 3 is greater than 1, it will skip to the else block. In this block, we see the line return n * getFactorialRecursively(n-1);.

We know the current value of n for the moment, it's 3, but getFactorialRecursively(n-1) is still to be calculated.

Then the program calls the same method once more, but this time our method takes 2 as the parameter. It checks the if block and skips to the else block and again encounters the last line. Now, the current value of the n is 2 but the program still must calculate the getFactorialRecursively(n-1).

So it calls the method once again, but this time the if block, or rather, the base class succeeds to return 1 and breaks out from the recursion.

Following the same pattern upwards, it returns each method result, multiplying the current result with the previous n and returning it for the previous method call. In other words, our program first gets to the bottom of the factorial (which is 1), then builds its way up, while multiplying on each step.

Also removing the method from the call stack one by one, up until the final result of the n * (n-1) is returned.

This is generally how recursive methods work. Some more complicated problems may require deeper recursions with more than one base case or more than one recursive step. But for now, this simple recursion is good enough to solve our factorial problem!

Calculating Factorial for Large Numbers

Factorials get large pretty quickly. Everyone knows how exponentials tend to get huge given a small number of steps:

$$
2^6 = 64
$$

$$
6! = 720
$$

As a matter of fact, a factorial of just 20 is equal to:

$$
20! = 2,432,902,008,176,640,000
$$

That's 2.4 quintillion. The next factorial is 51 quintillion, which is out of range even for longs in Java, which stands at ~9 quintillion. Integers run out at a mere 2.4 billion, so they're out of the question pretty quickly.

This is where a BigInteger comes into play - the JVM doesn't pre-allocate known space for the number and dynamically updates its size. You can fill the entire RAM with digits for a BigInteger and only then would you run into the limit:

public static BigInteger getFactorialRecursively(int n) {
    BigInteger value = BigInteger.valueOf(n);
    if (value == BigInteger.ZERO) {
        return BigInteger.ONE;
    } else {
        return value.multiply(getFactorialRecursively(n - 1));
    }
}

Chucking in 21 into this method would result in:

51090942171709440000

Conclusion

In this article, we covered how to calculate factorials using for and while loops. We also learned what recursion is, and how to calculate factorial using recursion.