#### Factorial, the recursive way

No. 108

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.