Factorial, the recursive way

exercise No. 110

Q:

We introduce a second strategy calculating a given argument's factorial by introducing recursive methods. Recursive programming is also a prerequisite for the later tic-tac-toe strategy exercise.

Recursive methods will call themselves. Recursive methods typically have:

  1. A recursive expression reducing a problem step by step.

  2. A termination condition.

With respect to calculating factorials this may be expressed as:

Reducing statement

n ! = n ( n - 1 ) .

Termination condition

0 ! = 1 .

This allows for calculating e.g. 4! in a recursive fashion:

4 ! = 4 × ( 4 - 1 ) ! Recursion 4 -> 3
= 4 × 3 × ( 3 - 1 ) ! Recursion 3 -> 2
= 4 × 3 × 2 × ( 2 - 1 ) ! Recursion 2 -> 1
= 4 × 3 × 2 × 1 × ( 1 - 1 ) ! Termination condition 0 ! = 1 .

Use the above scheme for implementing a second method static public long factorialRecurse(int n). The implementation should only use recursion and termination conditions but no loops whatsoever.

BTW: The concept of recursion in computer science is closely related to the mathematical concept of induction.

A:

The implementation is surprisingly simple:

static public long factorialRecurse(int n) {
  if (0 == n) {
    return 1;                           // Termination condition
  } else {
    return n * factorialRecurse(n - 1); // Reducing step: n! = n * (n - 1)!
}

If you fancy compact code you may as well write.

static public long factorialRecurse(int n) { return 0 == n ? 1: n * f(n - 1);}

Beware: The latter sacrifices both readability and the ability to debug for brevity. Your mileage may vary.