1.8 Recursive Factorials

Example 1-8 shows another way to compute factorials. This example uses a programming technique called recursion. Recursion happens when a method calls itself, or in other words, invokes itself recursively. The recursive algorithm for computing factorials relies on the fact that n! is equal to n*(n-1)!. Computing factorials in this fashion is a classic example of recursion. It is not a particularly efficient technique in this case, but there are many important uses for recursion, and this example demonstrates that it is perfectly legal in Java. This example also switches from the int data type, which is a 32-bit integer, to the long data type, which is a 64-bit integer. Factorials become very large, very quickly, so the extra capacity of a long makes the factorial( ) method more useful.

Example 1-8. Factorial2.java

package je3.basics;
/**
 * This class shows a recursive method to compute factorials.  This method
 * calls itself repeatedly based on the formula: n! = n * (n-1)!
 **/
public class Factorial2 {
    public static long factorial(long x) {
        if (x < 0) throw new IllegalArgumentException("x must be >= 0");
        if (x <= 1) return 1;              // Stop recursing here
        else return x * factorial(x-1);    // Recurse by calling ourselves
    }
}