Recursion - Java: How to Program Early Objects - page 781

...
12! = 479001600
...
20! = 2432902008176640000
21! = -4249290049419214848

12! causes overflow for int variables

21! causes overflow for long variables

Fig. 18.3 | Recursive factorial method. (Part 2 of 2.)

Common Programming Error 18.1
Either omitting the base case or writing the recursion step incorrectly so that it does not
converge on the base case can cause a logic error known as infinite recursion , where re-
cursive calls are continuously made until memory is exhausted or the method-call stack
overflows. This error is analogous to the problem of an infinite loop in an iterative (non-
recursive) solution.

Method main (lines 16-21) displays the factorials of 0-21. The call to the factorial
method occurs in line 20. Method factorial receives a parameter of type long and
returns a result of type long . The program's output shows that factorial values become
large quickly. We use type long (which can represent relatively large integers) so the pro-
gram can calculate factorials greater than 12!. Unfortunately, the factorial method pro-
duces large values so quickly that we exceed the largest long value when we attempt to
calculate 21!, as you can see in the last line of the program's output.
Due to the limitations of integral types, float or double variables may ultimately be
needed to calculate factorials of larger numbers. This points to a weakness in some pro-
gramming languages—namely, that they aren't easily extended with new types to handle
unique application requirements. As we saw in Chapter 9, Java is an extensible language
that allows us to create arbitrarily large integers if we wish. In fact, package java.math pro-
vides classes BigInteger and BigDecimal explicitly for arbitrary precision calculations that
cannot be performed with primitive types. You can learn more about these classes at

docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html
docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html

18.4 Reimplementing Class FactorialCalculator
Using Class BigInteger
Figure 18.4 reimplements class FactorialCalculator using BigInteger variables. To
demonstrate larger values than what long variables can store, we calculate the factorials of
the numbers 0-50. Line 3 imports class BigInteger from package java.math . The new
factorial method (lines 8-15) receives a BigInteger as an argument and returns a
BigInteger .

1 // Fig. 18.4: FactorialCalculator.java

2 // Recursive factorial method.

3
4

import java.math.BigInteger;

Fig. 18.4 | Factorial calculations with a recursive method. (Part 1 of 2.)