☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Factorial of a given number

Easy TUF ID 371 A2Z

Java source ↗ Edit this article ↗

Problem

Given a non-negative integer N, return its factorial N! = 1 × 2 × 3 × ... × N. By definition 0! = 1 (the empty product).

Some sheets phrase the row as “find all factorial numbers less than or equal to N”, where a factorial number is any value of the form k!: 1, 2, 6, 24, 120, .... We solve the main problem with three approaches and cover the variant at the end, since it falls out of the same loop.

Constraints: 0 ≤ N ≤ 20. The bound is not arbitrary: 20! is about 2.4 × 10^18, the largest factorial that fits in a 64-bit long; 21! overflows. Already 13! overflows a 32-bit int, so every method returns long.

Example 1

N = 5
answer = 120              // 1 * 2 * 3 * 4 * 5

Example 2

N = 0
answer = 1                // the empty product is 1 by convention

Example 3

N = 20
answer = 2432902008176640000   // the largest factorial that fits in a long

Approach 1: Loop

Intuition. Keep a running product and multiply in 2, 3, ..., N. Starting the loop at 2 (rather than 1) saves a pointless multiplication and makes N = 0 and N = 1 fall out naturally: the loop body never runs and the initial value 1 is returned.

Algorithm.

  1. Set result = 1.
  2. For i from 2 to N, do result *= i.
  3. Return result.
static long iterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

Complexity. Time O(n): one multiplication per number. Space O(1).

Approach 2: Functional recursion

Intuition. The factorial has a recursive definition: n! = n × (n - 1)! with 0! = 1. Translate it literally. The call for n trusts that the call for n - 1 returns the correct smaller factorial and multiplies it by n after that call returns. This is functional recursion: the function’s return value is the answer, and the combination step happens on the way back up the stack.

The base case n <= 1 covers both 0! = 1 and 1! = 1, and also stops the recursion for negative input instead of running forever.

Algorithm.

  1. If n <= 1, return 1.
  2. Otherwise return n * recursive(n - 1).
static long recursive(int n) {
    if (n <= 1) return 1;                   // base case: 0! = 1! = 1
    return n * recursive(n - 1);
}

Dry run on N = 4:

call returns
recursive(4) 4 * recursive(3) = 4 * 6 = 24
recursive(3) 3 * recursive(2) = 3 * 2 = 6
recursive(2) 2 * recursive(1) = 2 * 1 = 2
recursive(1) 1 (base case)

Note that n is an int and recursive(n - 1) is a long, so the multiplication is performed in long. That is what keeps 20! from overflowing.

Complexity. Time O(n): n calls. Space O(n) for the call stack; every frame must stay alive until its callee returns because it still has a multiplication to do.

Approach 3: Parameterised (tail) recursion

Intuition. Instead of multiplying on the way back, carry the product so far down into the recursion as a parameter. Each call multiplies the current i into the accumulator and passes it on; the base case has nothing left to multiply and simply returns the accumulator. Nothing happens after the recursive call, so the answer is complete at the bottom and is handed back untouched. This is the same shape as a loop, with the loop variable and the accumulator turned into parameters.

Algorithm.

  1. Start with multiplyDown(n, 1).
  2. In multiplyDown(i, product): if i <= 1, return product.
  3. Otherwise return multiplyDown(i - 1, product * i).
static long tailRecursive(int n) {
    return multiplyDown(n, 1);
}

private static long multiplyDown(int i, long product) {
    if (i <= 1) return product;             // base case: everything has been multiplied in
    return multiplyDown(i - 1, product * i);
}

Complexity. Time O(n). Space O(n) on the JVM, which does not eliminate tail calls; in a language that does, this version would run in O(1) space, which is the practical reason to know the shape.

Variant: all factorial numbers up to a limit

Intuition. If the sheet asks for every k! that does not exceed limit, generate factorials in increasing order with the same running product and stop at the first one that is too big. Because factorials grow so fast, there are never more than 20 of them within long range, so the loop is tiny.

The one subtlety is overflow: for a huge limit the running product could wrap around to a negative number, which would compare as “still small” and corrupt the output (and could even loop forever, because k! for k ≥ 66 has so many factors of two that the wrapped long becomes 0). Checking fact > Long.MAX_VALUE / i before the multiplication detects the overflow one step early.

static List<Long> factorialsUpTo(long limit) {
    List<Long> out = new ArrayList<>();
    long fact = 1;
    for (int i = 2; fact <= limit; i++) {
        out.add(fact);
        if (fact > Long.MAX_VALUE / i) break;   // the next factorial would overflow long
        fact *= i;
    }
    return out;
}

For limit = 6 this returns [1, 2, 6]; for limit = 100 it returns [1, 2, 6, 24]; for limit = 0 it returns an empty list; for limit = Long.MAX_VALUE it returns exactly 1! through 20!.

Complexity. Time O(k) for k results, which is at most 20. Space O(k) for the output.

Edge cases and pitfalls