17.6. Recursive Factorial

Problem: What is the factorial of the non-negative integer n?

• By definition, the first number in the factorial sequence is 1.

• Example:

  0! = 1 (base case)
  1! = 0! * 1 = 1 * 1
  2! = 1! * 2 = 1 * 1 * 2
  3! = 2! * 3 = 1 * 1 * 2 * 3
  4! = 3! * 4 = 1 * 1 * 2 * 3 * 4
  

Given the above problem description, identify the base cases and the recursive cases. Now, try to write a method called factorial that takes a single int argument, n, and returns n! as a long.

Don’t read beyond this point until you’ve attempted to write the recursive factorial method.

Sample Solution

long factorial(int n) {
    if (n == 0) return 1;           // base case
    return n * factorial(n - 1);    // recursive case
} // factorial

Sample Recursion Tree

Here is a sample recursion tree for factorial(3):

factorial(3)
     \
3 * factorial(2)
         \
     2 * factorial(1)
              \
          1 * factorial(0)
                   \
                    1

Sample Call Stack

The recursion tree above only shows the method calls. Notice how the multiplications are shown to the side. It is interesting to note that these multiplications, although written in a return statement on the same line as the recursive call, are actually evaluated after the associated recursive call returns (just as with the print statements in the countFrom example). To help us better understand what is going on, step-by-step, here is a depiction of how the call stack changes as the recursive method calls approach and reach the base case for factorial(3):

 immediately             immediately             immediately             immediately
 after calling           after calling           after calling           after calling
 factorial(3)            factorial(2)            factorial(1)            factorial(0)
|------------------|    |------------------|    |------------------|    |------------------|
| [calling method] | => | [calling method] | => | [calling method] | => | [calling method] |
|------------------|    |------------------|    |------------------|    |------------------|
| [factorial(3)]   |    | [factorial(3)]   |    | [factorial(3)]   |    | [factorial(3)]   |
| n = 3            |    | n = 3            |    | n = 3            |    | n = 3            |
| return 3 * ?     |    | return 3 * ?     |    | return 3 * ?     |    | return 3 * ?     |
|------------------|    |------------------|    |------------------|    |------------------|
                        | [factorial(2)]   |    | [factorial(2)]   |    | [factorial(2)]   |
                        | n = 2            |    | n = 2            |    | n = 2            |
            | return 2 * ?     |    | return 2 * ?     |    | return 2 * ?     |
                        |------------------|    |------------------|    |------------------|
                                                | [factorial(1)]   |    | [factorial(1)]   |
                                                | n = 1            |    | n = 1            |
                        | return 1 * ?     |    | return 1 * ?     |
                                                |------------------|    |------------------|
                                                                        | [factorial(0)]   |
                                                                        | n = 0            |
                                    | return 1         |
                                                                        |------------------|

As the recursive method calls return back to their calling methods, we begin to see the program perform the multiplications to produce the return values:

 immediately             immediately             immediately             immediately
 after returning         after returning         after returning         after returning
 factorial(0)            factorial(1)            factorial(2)            factorial(3)
|------------------|    |------------------|    |------------------|    |------------------|
| [calling method] | => | [calling method] | => | [calling method] | => | [calling method] |
|------------------|    |------------------|    |------------------|    |------------------|
| [factorial(3)]   |    | [factorial(3)]   |    | [factorial(3)]   |
| n = 3            |    | n = 3            |    | n = 3            |     Now has value 6
| return 3 * ?     |    | return 3 * ?     |    | return 3 * 2 = 6 |
|------------------|    |------------------|    |------------------|
| [factorial(2)]   |    | [factorial(2)]   |
| n = 2            |    | n = 2            |
| return 2 * ?     |    | return 2 * 1 = 2 |
|------------------|    |------------------|
| [factorial(1)]   |
| n = 1            |
| return 1 * 1 = 1 |
|------------------|

After all of our recursive calls are complete, the value 6 is what is ultimately returned to the main method.

Congratulations! You now have a basic understanding of recursion!