1.8 Recursive Factorials
Example 18 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*(n1)!.
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 32bit
integer, to the long data type, which is a 64bit
integer. Factorials become very large, very quickly, so the extra
capacity of a long makes the factorial(
) method more useful.
Example 18. 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 * (n1)!
**/
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(x1); // Recurse by calling ourselves
}
}
