RECURSION - Introduction to Java Programming: Comprehensive Version - page 707

else
return n * factorial(n - 1 );

A recursive call can result in many more recursive calls, because the method keeps on dividing
a subproblem into new subproblems. For a recursive method to terminate, the problem must
eventually be reduced to a stopping case, at which point 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 by the result of factorial(n - 1) .
Listing 18.1 gives a complete program that prompts the user to enter a nonnegative integer
and displays the factorial for the number.

L ISTING 18.1

ComputeFactorial.java
1 import java.util.Scanner;
2
3 public class ComputeFactorial {
4 /** Main method */
5 public static void main(String[] args) {
6 // Create a Scanner
7 Scanner input = new Scanner(System.in);
8 System.out.print( "Enter a nonnegative integer: " );
9 int n = input.nextInt();

10
11 // Display factorial
12 System.out.println( "Factorial of " + n + " is " + factorial(n));
13 }
14
15

/** Return the factorial for the specified number */

16 public static long factorial( int n) {

17 if (n == 0 ) // Base case base case

18 return 1 ;

19 else

20 return n * factorial(n - 1 ); // Recursive call recursion

21 }
22 }

Enter a nonnegative integer: 4
Factorial of 4 is 24

Enter a nonnegative integer: 10
Factorial of 10 is 3628800

The factorial method (lines 16-21) 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 .
You see how to write a recursive method. How does recursion work behind the scenes?
Figure 18.2 illustrates the execution of the recursive calls, starting with n = 4 . The use of
stack space for recursive calls is shown in Figure 18.3.

how does it work?