Implementing the Factorial Function Using Java and Guava

What I like with factorial function is that it’s easy to implement by using different approaches. This month, I’ve presented functional programming and some of its main concepts (recursion, tail recursion optimization, list processing) through different ways to code the factorial function. After the presentation, I’ve asked the audience to implement the factorial by using a recursive and a tail recursive approaches, with Java alone, then with Guava’s Function interface.

In this post, we see the solutions of the exercises I’ve proposed and some explanation about the functional programming concepts used.

Factorial

Here is a reminder of the behavior of the factorial:

The factorial of a given integer n (or n!) is the product of the integers between 1 and n.

In imperative style, you write the factorial like this:

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

The recursive solution in Java

The previous implementation of factorial is based explicitly on state manipulation: the variable result is changed successively in the for loop at each iteration. The functional approach dislike particularly the explicit manipulation of a state in the body of a function. Usually, functional programming prohibits the use of loops like for, while, repeat, etc., for this reason. The only way to express a loop is to use recursion (ie. a function that calls itself).

In Mathematics, you express the factorial recursively like this:

0! = 1
n! = n . (n – 1), for n > 0

Or in plain English:

The factorial of 0 is 1 and the factorial of n is the product between n and the factorial of the preceding integer.

The implementation in Java of the recursive factorial is closed to the mathematic definition:

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

Recursive solution in Guava

Guava proposes a function representation as object. It’s based on the generic interface Function<T, R>. It looks like this very simple implementation:

public interface Function<T, R> {
    R apply(T value);
}

T is the input type and R the returned type of the function. If you create an instance based on the interface Function, you’ve to defined the method apply(), that represents the body of the function. Here’s the implementation of the recursive version of factorial based on Guava:

Function<Integer, Integer> factorial = new Function<Integer, Integer>() {
    @Override public Integer apply(Integer n) {
        if (n == 0) return 1;
        else return n * apply(n - 1);
    }
};

If you want to use this function, you’ve to write this:

Integer result = factorial.apply(5);

The Guava approach has this particularity to allow you to declare recursive and anonymous functions:

Integer result = new Function<Integer, Integer>() {
    @Override public Integer apply(Integer n) {
        if (n == 0) return 1;
        else return n * apply(n - 1);
    }
}.apply(5);

Tail recursion in Java

There’s another way to implement the recursive version of the factorial. This approach consists in having the recursive call executed just before to return from the function. There must have no other instruction to execute between the recursive call and the return instruction. This approach is called tail recursion. The previous implementation isn’t a case of tail recursion, because you have to execute a multiplication between n and the value returned by the recursive call before to exit the function.

In order to implement a tail recursive factorial, we have to introduce a second parameter (named k) to the function. This parameter contains the partial result of the function through the successive recursive calls. Once the stop condition is reached, k contains the final result. Below, you’ve the implementation of the tail recursive factorial:

private static int fact(int n, int k) {
    if (n == 0) return k;
    else return fact(n - 1, n * k);
}

public static int factorial(int n) {
    return fact(n, 1);
}

Notice that for the first call, the parameter k is initialized to 1. This relates to the basis case: when n is 0 then the function should return 1.

Motivation behind the tail recursion

There’s an important difference in behavior between the recursive and the tail recursive implementations. These difference is visible through the the call stack. In the recursive case, the result is built as you come back from recursive calls. Here is the different states of the call stack in recursive version when we call factorial(5):

-> factorial(5)  // first call
  -> factorial(4)
    -> factorial(3)
      -> factorial(2)
        -> factorial(1)
          -> factorial(0)  // here, we've reached the stop condition
          <- 1
        <- 1 = 1 * 1  // all remaining multiplications are executed
      <- 2 = 2 * 1
    <- 6 = 3 * 2
  <- 24 = 4 * 6
<- 120 = 5 * 24  // we have computed the result in the last return

Now, you can see the call stack for the tail recursive implementation for the same call:

-> fact(5, 1)  // first call
  -> fact(4, 5)  // result is built through the successive calls
    -> fact(3, 20)
      -> fact(2, 60)
        -> fact(1, 120)
          -> fact(0, 120)  // here, we've reached the stop condition
          <- 120  // the final result is obtained directly in the last recursive call
        <- 120
      <- 120
    <- 120
  <- 120
<- 120

You can notice that when we’re coming back from the recursive calls here, the same value is returned. Thus, we can easily imagine to optimize the tail recursive implementation. In fact, there two possible optimizations at this level. The first one is call trampolining. It consists in generating some small modification where recursive call is marked bounce and return is marked landing. Then an external fonction is used to emulate the recursive calls based on a while loop.

The second optimization uses a deeper transformation of the source code, where the while loop is directly put inside the function body. For the tail recursive implementation of the factorial function, this second optimization would turn our source code into this:

public static int factorial(int n, int k) {
    while (!(n == 0)) {
        k = n * k;
        n = n - 1;
    }
    return k;
}

These optimizations prevent the deep use of the call stack. Thus, you have no occurrence of stack overflow. But, you might have an infinite loop if you mistype the stop condition. The advantage of the second optimization over the first one and all recursive implementations is that it’s really quick as there’s no use of the call stack. A language like Scala proposes this second optimization by default. A precise look at the produced bytecode shows the transformation of the recursive call into a goto.

These optimizations aren’t present in Java.

Notice that not all recursive functions can be converted to a tail recursive function. This is the case of the function that computes the Fibonnacci series. It based on the jonction of two recursive calls.

public static fib(int n) {
    if (n <= 1) return 1;
    else return fib(n-1) + fib(n-2);
}

Tail recursion in Guava

We’ve seen that the tail recursive implementation of the factorial needs two parameters. But in Guava, you can only define functions that accept a unique argument! So how do we do to transform a function of one argument into a function of two arguments?

There are two possibilities. The first one consists in creating a class that represents a pair of elements. Thus a function that takes two arguments is equivalent to a function that takes a pair of elements. The second possibility consists in using the curryfication. The curryfication is a use case of the higher order functions. With this, a function that takes many arguments is converted into a function that takes the first argument, and return a function that takes the second argument, and so on till we get the last argument. For example, the addition function (add) is typically a function of two arguments (a and b). You can write add in such a way that add takes a and return a function that waits for b. Once you get b, the function is evaluated. The interest of such an approach isn’t to force you to provide all parameters of a function at the same time. For our add function, you can use add directly to execute an addition: add.apply(1).apply(3) == 4. Or you can use add to define the function add_one just by providing the first parameter only: add_one = add.apply(1). Then, you can provide the second parameter when you want through add_one: add_one.apply(3) == 4.

Below is the implementation of tail recursive factorial based on Guava. The signature of this function is Function<Integer, Function<Integer, Integer>>. Here, you’ve to understand:

factorial is a function that takes a first parameter n and returns another function that takes a second parameter k and returns the factorial of n.

public class FactorialFunction implements Function<Integer, Function<Integer, Integer>> {
    @Override
    Function<Integer, Integer> apply(final Integer n) {
        return new Function<Integer, Integer>() {
            @Override
            public Integer apply(Integer k) {
                if (n == 0) return k;
                else return FactorialFunction.this.apply(n - 1).apply(k * n);
            }
        };
    }
}

FactorialFunction fact = new FactorialFunction();
Integer result = fact.apply(5).apply(1); // factorial of 5

Notice the use of FactorialFunction.this in order to use the outer object in the inner one. You have to reference the outer object in order to set all parameters before the recursive call. This forces you to create a named class to represent your factorial function.

Compare this implementation with the implementation below in Haskell, which is tail recursive and curryfied already. They’re both equivalent:

fact n k = if n == 0
  then k
  else fact (n-1) (n*k)

In fact, there are differences in the Guava implementation: it isn’t optimized and you create a new object for each recursive call.

Advertisement