Factorial Using Iteration, Recursion and Java 8 Streams

In this post, we will solve the classic school problem of calculating the factorial of a positive integer, using different Java algorithms.

Note: In all the algorithms below, we assume that the input is > 1.

1. Iterative Factorial

In this algorithm, we use a standard for-loop and increment the variables i and result at each iteration:

static int iterativeFactorial(final int n) {
  int result = 1;
  for (int i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

2. Recursive Factorial

Here is the recursive version (the function calls itself):

static int recursiveFactorial(final int n) {
  return n == 1 ? 1 : n * recursiveFactorial(n - 1);
}

Recursion lets you get rid of variables that are updated at each iteration. Typically, making a recursive function call is more expensive than iteration because each time the function is called, a new stack frame has to be created on the call stack to hold the state of each function call. Therefore, the memory consumed by the recursive function is proportional to the size of its input. You may even get a StackOverflowError with a large input.

3. Tail-recursive Factorial

Here's a tail-recursive definition of factorial. The recursive call is the last thing that happens in the function. In contrast, in our previous definition of factorial, the last thing was n multiplied by the result of the recursive call.

static int tailRecursiveFactorial(final int n) {
  return tailRecursiveFactorialHelper(n, 1);
}
private static int tailRecursiveFactorialHelper(final int n, final int acc) {
  return n == 1 ? acc : tailRecursiveFactorialHelper(n - 1, n * acc);
}

Tail-recursive functions can be optimised by the compiler in some programming languages. Instead of storing each intermediate result of the recursion onto different stack frames, a single stack frame can be reused instead, because there's no need to keep track of intermediate results. Unfortunately, Java does not support this kind of optimisation, but you might want to take this approach anyway, in case the compiler is optimised in the future. Other JVM languages (e.g. Scala) can optimise tail-recursion.

4. Stream Factorial

Finally, Java 8 streams provide a simple, declarative way of defining factorial:

static int streamFactorial(final int n) {
  return IntStream.rangeClosed(1, n).reduce(1, (a, b) -> a * b);
}

Factorial Algorithm

The factorial of a number is the product of all positive integers less than or equal to it. e.g. the factorial of 5 is 5 x 4 x 3 x 2 x 1 = 120.

While conducting a Java interview, I like to ask my candidates to write an algorithm to calculate the factorial of a number. This is one of my favourite questions because it gives me an insight into their thinking process. It is also one of the questions that I was asked at Merrill Lynch, in my first interview out of university. (I got it right)

I am surprised at how the majority of people cannot answer this question, or get anywhere close to it. C'mon, you can do it using recursion or loop-iteration; its not that difficult! If you can't count backwards, do it forwards - its the same thing.

Here is a simple solution: //loop public int factorial(int n) { int result = 1 ; for(int i = n ; i > 0 ; i--) { result = result * i ; } return result ; } //recursion public int recursiveFactorial(int n) { if (n == 0) return 1 ; else return n * recursiveFactorial(n-1) ; }