Factorial Program in Java: Loop, Recursion, Streams and BigInteger

The factorial of n, written n!, is 1 × 2 × … × n, with 0! = 1. It grows fast enough that the Java question is really about when it stops fitting: int breaks at 13!, long breaks at 21!, and only BigInteger gives you 100! (158 digits).

Tested on OpenJDK 21.0.12. All output on this page comes from FactorialPrograms.java. The overflow points were also confirmed with Python’s exact integers. Java does not warn on overflow: 13! in int prints 1932053504, with no error.

Iterative: the loop

Multiply a running result by 2, 3, …, n. Starting result at 1 handles 0! = 1! = 1 without a special case.

static long factorialLoop(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Source: FactorialPrograms.java.

Recursive

Define n! = n × (n−1)! with the base case n ≤ 1. It reads like the maths but uses one stack frame per level.

static long factorialRecursive(int n) {
    if (n <= 1) return 1;                 // base case: 0! = 1! = 1
    return n * factorialRecursive(n - 1);
}

Source: FactorialPrograms.java.

Recursion also has a ceiling that is not about numbers: the program tried a recursive BigInteger factorial of 1,000,000 and Java threw StackOverflowError (output below). The iterative version computed 5,000! without trouble.

With streams

LongStream.rangeClosed(1, n).reduce(1L, (a, b) -> a * b) is the same loop in functional form. It overflows exactly like the loop does. See Top 50 Java Stream API coding interview questions for more.

static long factorialStream(int n) {
    return LongStream.rangeClosed(1, n).reduce(1L, (a, b) -> a * b);
}

Source: FactorialPrograms.java.

Where int and long overflow

Each bar is one factorial on a log scale. The green bars (1 to 12) fit in int, the amber ones (13 to 20) need long, and from 21 even long wraps around. The table below is the program’s own output: the first column is the true value, the next two are what Java actually computed.

n    n! (true)                int arithmetic           long arithmetic
10   3628800                  3628800                  3628800
12   479001600                479001600                479001600
13   6227020800               1932053504               6227020800
15   1307674368000            2004310016               1307674368000
20   2432902008176640000      -2102132736              2432902008176640000
21   51090942171709440000     -1195114496              -4249290049419214848
22   1124000727777607680000   -522715136               -1250660718674968576

Source: FactorialPrograms.java.

Note the long column at 21 and 22: negative numbers, produced silently. Math.multiplyExact makes the failure loud:

static long factorialExact(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result = Math.multiplyExact(result, (long) i);   // throws on overflow
    }
    return result;
}

int overflows first at n = 13   (12! = 479001600 fits, int max = 2147483647)
long overflows first at n = 21   (20! = 2432902008176640000 fits, long max = 9223372036854775807)
factorialExact(21) -> java.lang.ArithmeticException: long overflow

Source: FactorialPrograms.java.

For overflow in plain addition, see Add two integers in Java without overflow (addExact, BigInteger).

BigInteger: factorial of 100 and beyond

BigInteger.multiply returns a new number each time and has no size limit. The stream version reduces a range of BigIntegers with multiply; the program checks both give the same 100!.

static BigInteger factorialBig(int n) {
    BigInteger result = BigInteger.ONE;
    for (int i = 2; i <= n; i++) {
        result = result.multiply(BigInteger.valueOf(i));
    }
    return result;
}

static BigInteger factorialBigStream(int n) {
    return IntStream.rangeClosed(2, n)
                    .mapToObj(BigInteger::valueOf)
                    .reduce(BigInteger.ONE, BigInteger::multiply);
}

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
100! has 158 digits; stream version equal: true

recursive factorial of 1,000,000 -> StackOverflowError
iterative BigInteger 5000! has 16326 digits

Source: FactorialPrograms.java.

Common interview questions

Common mistakes

• Using int for the result because the input is an int.
• Not handling 0 and negative input. Factorial is undefined for negatives; throw IllegalArgumentException.
• Trusting negative output. A negative factorial means overflow.
• Recursing with BigInteger for large n. You trade a number limit for a stack limit.
• Forgetting the base case and getting infinite recursion.

FAQ

How do I find the factorial of a number in Java?

Loop from 2 to n multiplying a result that starts at 1, using long or BigInteger.

How do I compute 100 factorial in Java?

With BigInteger; 100! has 158 digits and does not fit in any primitive type.

Why does my factorial program print a negative number?

The result overflowed. int overflows at 13! and long at 21!.

Further reading

• FactorialPrograms.java — all versions
• Add two integers in Java without overflow
• Fibonacci series in Java
• Number programs in Java (strong numbers use factorials)
• Prime numbers in Java
• Top 40 Java concurrency interview questions
• Top 50 Java Stream API coding interview questions
• Math.multiplyExact, Java 21 API