21.6. Wildcards

[Page 636 ( continued )]

19.2. Example: Factorials

Many mathematical functions are defined using recursion. The factorial of a number n can be recursively defined as follows :

   0! = 1;     n! = n x (n - 1)!; n > 0   

How do you find n! for a given n ? It is easy to find 1! because you know that 0! and 1! is 1 x 0! . Assuming that you know (n-1)! , n! can be obtained immediately using n x(n - 1)! . Thus, the problem of computing n! is reduced to computing (n - 1)! . When computing (n - 1)! , you can apply the same idea recursively until n is reduced to .

Let factorial(n) be the method for computing n! . If you call the method with n = 0 , it immediately returns the result. The method knows how to solve the simplest case, which is referred to as the base case or the stopping condition . If you call the method with n > 0 , it reduces the problem into a subproblem for computing the factorial of n - 1 . The subproblem is essentially the same as the original problem, but is simpler or smaller than the original. Because the subproblem has the same property as the original, you can call the method with a different argument, which is referred to as a recursive call .

The recursive algorithm for computing factorial(n) can be simply described as follows:

   if   (n ==     )   return 1   ;   else     return   n * factorial(n -   1   ); 

A recursive call can result in many more recursive calls because the method is dividing a subproblem into new subproblems. For a recursive method to terminate, the problem must eventually be reduced to a stopping case. When it reaches a stopping case, the method returns a result to its caller. The caller then performs a computation and returns the result to its own caller. This process continues until the result is passed back to the original caller. The original problem can now be solved by multiplying n with the result of factorial(n - 1) .

Listing 19.1 gives a complete program that prompts the user to enter a non-negative integer and displays the factorial for the number.

Listing 19.1. ComputeFactorial.java

(This item is displayed on pages 636 - 637 in the print version)

 1   import   javax.swing.JOptionPane; 2 3   public class   ComputeFactorial { 4  /** Main method */  5   public static void   main(String[] args) { 6  // Prompt the user to enter an integer  7 String intString = JOptionPane.showInputDialog( 8   "Please enter a non-negative integer:"   ); 9 

---

[Page 637]

 10  // Convert string into integer  11   int   n = Integer.parseInt(intString); 12 13  // Display factorial  14 JOptionPane.showMessageDialog(   null   , 15   "Factorial of "   + n +   " is "   +  factorial(n)  ); 16 } 17 18  /** Return the factorial for a specified number */  19   public static long    factorial(   int   n)  { 20   if   (n ==     )  // Base case  21   return 1   ; 22   else   23   return   n *  factorial(n -   1   )  ;  // Recursive call  24 } 25 } 

The factorial method (lines 19 “24) is essentially a direct translation of the recursive mathematical definition for the factorial into Java code. The call to factorial is recursive because it calls itself. The parameter passed to factorial is decremented until it reaches the base case of 0.

Figure 19.1 illustrates the execution of the recursive calls, starting with n = 4 . The use of stack space for recursive calls is shown in Figure 19.2.

Figure 19.1. Invoking factorial(4) spawns recursive calls to factorial .

Figure 19.2. When factorial(4) is being executed, the factorial method is called recursively, causing memory space to dynamically change.

(This item is displayed on page 638 in the print version)

Caution

Infinite recursion can occur if recursion does not reduce the problem in a manner that allows it to eventually converge into the base case. For example, if you mistakenly write the factorial method as follows:

   public static long    factorial(  int  n)  {   return   n *  factorial(n -   1   )  ; } 

The method runs infinitely and causes a StackOverflowError .

---

[Page 638]

Pedagogical Note

It is simpler and more efficient to implement the factorial method using a loop. However, the recursive factorial method is a good example to demonstrate the concept of recursion.