HowWhy (not) to write Factorial in Java.

In “Development Chaos Theory”, William Woody laments the habits of bad Java programmers. I blame the language.

Before I start ranting, let me first say that I agree completely with Mr. Woody. If you haven't read his article, I suggest you do now.

Let's follow the example.

/** 
 * @author wwoody
 */
public static int factorial(int n)
{
    if (n == 0) return 1;
    return n * factorial(n-1);
}

This is presented as a typical way someone might write this in Java. I might have written it slightly differently:

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

There is only a subtle difference between these. return, in its fully general form, is a non-local exit. It returns out of the enclosing method instead of out of the enclosing form. The difference becomes obvious if you attempt to manually inline the factorial method.

public static foo (int x)
{
    int y = (x == 0) ? 1 : x * factorial (x - 1);
    ...etc.
}

public static bar (int x)
{
    int y = if (x == 0) return 1;
            return n * factorial(n-1);
    ...etc.
}

Either way appears to be acceptable Java to me.

There should already be warning bells ringing. I have to admit that I didn't hear them the first time I looked at this code, though. I'm so inured to this crap that I missed a glaring problem.

Simplicio: Why do these methods have type declarations?
Salviati: Java doesn't do type inference.

Simplicio: Ok, that's lame, but why not just declare everything to be Object?
Salviati: Objects are too general. The * method doesn't work on them.

Simplicio: Of course! We want the most general type that supplies ==, *, and - operations. So let's use Number.
Salviati: Hold your horses, cowboy. Arithmetic doesn't work on Numbers.

Simplicio: What? Whyever not?!
Salviati: Arithmetic only works on byte, double, float, int, long, and short.

Simplicio: factorial should work on any of these. Why do I have to pick one?
Salviati: The semantics of these types aren't compatible. They behave quite differently at the very ends of their ranges. There is no way to unify them under a superclass and still preserve the subclass semantics.

Simplicio: umm... whatever. What about that static thingy?
Salviati: That doesn't matter. You aren't using any objects.

Simplicio: If it doesn't matter, why do I have to specify it?
Salviati: It would matter if you were using objects. It tells the compiler that free identifiers should have class scope. By specifying static, you're indicating that you want lexical scope.

Simplicio: But that doesn't matter because I'm not using any objects.
Salviati: Right.

Simplicio: If it doesn't matter, why do I have to specify it?

Then Mr. Woody wraps the method in a utility class:

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }
}

and suggests an iterative implementation

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}

Simplicio: Ummm....
Salviati: You don't want to know. In this case, we're not really using the class, but you'll want it later to avoid namespace conflicts.

Simplicio: I guess... Isn't namespace management is more of a configuration control issue than a datatype issue? Wouldn't I want these to be orthogonal issues?
Salviati: They can be handled orthogonally, but that requires some serious hacking. Right now all you want is a simple factorial problem, so just use the default.

Simplicio: What default?
Salviati: Just pick a name. Remember, though, the class name should be the same as the file name.

Simplicio: If it is the default, why do I have to do anything?

Mr. Woody now suggests that BigInteger is the right return type. We'll fix the code:

public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        if (n == 0) return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorial(n-1));
    }
}

alternatively...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

What we're seeing here is already serious problem. Changing the range of the output is a trivial change, yet it requires large changes to the code. Here we have the original code and the modified code with the changes highlighted.

// before changes...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}
// after changes...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

Sometimes, when you are building a big system, you want to transparently install a far-reaching package. This doesn't happen often, but it happens more often than you might think. Take, for example, the scmutils library. This library augments the standard generic arithmetic in MIT Scheme so that the usual arithmetic operators can handle vectors, matrices, and functions in addition to integers, rationals and reals. No changes need to be made to the code that calls the arithmetic methods. This makes life a lot easier for developers who will not have to remember whether to use the built-in arithmetic or to switch to the extended package.


Mr. Woody now points out that one might want to memoize the answers.

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    static HashMap cache = new HashMap();

    public static BigInteger factorial(int n)
    {
        BigInteger ret;

        if (n == 0) return BigInteger.ONE;
        if (null != (ret = cache.get(n))) return ret;
        ret = BigInteger.valueOf(n).multiply(factorial(n-1));
        cache.put(n, ret);
        return ret;
    }
}

To quote, “easy enough.”

Except it isn't. Memoization is a general technique that has nothing to do with the factorial program. Yet it isn't abstracted out of the problem. Tom White wrote an article on how to use Dynamic Proxy Classes to perform this abstraction. The code is a bit convoluted, but that doesn't matter because when all is said and done, we can just memoize that call to factorial.

That's the theory, anyway. It turns out that you'll need to build an interface to the factorial class and then memoize that:

/** 
 * @author wwoody
 */
public interface FactorialAlgorithm 
{
  public BigInteger factorial(final int n);
}

/** 
 * @author wwoody
 */
public class FactorialUtil implements FactorialAlgorithm
{
    public BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

FactorialAlgorithm originalFactorial = new FactorialUtil();
FactorialAlgorithm memoizedFactorial =
   (FactorialProgram) Memoizer.memoize(new FactorialUtil());

That's better, but there's still a problem. All the places in the code where you used to call FactorialUtil.factorial(n) now need to change to use the interface instead: memoizedFactorial.factorial(n). And every caller has to have access to an instance of the dynamic proxy class at runtime.

Let's continue. Mr. Woody points out that we want to select which version of factorial to use at runtime. After all, we don't even need the BigInteger version if the actual data only contains single digit numbers. To do this, he suggests a factory class that can examine configuration data and instantiate the appropriate implementation. I won't bore you with the details.

Mr. Woody then asserts:

Sure, there are circumstances where a pluggable architecture would be desirable or even necessary—but that comes up so rarely it’s not even funny. About 99% of the time I see code like this, it’s completely and utterly useless. It’s obscuring the purpose of the code—replacing a two or three line utility (max!) with dozens or even hundreds of lines of self-important masturbatory Java bullshit. Sure, it may make you feel good—but it makes an ugly mess of it that future developers will have to clean up, or more likely just avoid like the plague.

Again, I want to stress that I agree with Mr. Woody and I'm not attempting to argue against him. And here I'd like to interject and raise a point. What about the rare situations? About 1% of the time you really do want a pluggable architecture, and code like this is not completely useless. The problem is that you still need “dozens or even hundreds of lines of self-important masturbatory (but necessary) Java bullshit.” Since there is a need for a pluggable architecture, you can be sure that future developers won't be trying to clean it up. Unfortunately, that leaves “avoid like the plague” as our option.

Mr. Woody says:

The biggest complaint I have with many Java developers is that they develop a whole bunch of really bad habits. Specifications are unclear, or they think someday the code may need to be extended into a different direction. So they write a whole bunch of overblown architectural nonsense, sight unseen, thinking that the additional crap someday will help out and make things easier.

But how does this differ from the case where the additional crap really does make things easier? The code doesn't change simply because it becomes more useful. It is still a whole bunch of overblown architectural nonsense. The only difference is that you are forced to use this crap because it is the only way to get things done when the simple solution is insufficient.

My complaint with Java is that it tends to exacerbate a bad situation. Small conceptual changes to code, like changing an int to a BigInteger, end up being large textual changes. Larger conceptual changes, like adding a Factory object or a dynamically pluggable implementation, cannot be abstracted out. This leads to big piles of additional crap that have to be replicated all over the place. The language is unfriendly to change and modern software development is all about managing changes to the body of code.