Factorial, the recursive way

exercise No. 115

Q:

Disclaimer: Calculating factorials using recursion is ways inefficient. However it allows for an easy demonstration of the underlying principle. This prepares for programming tasks where recursion is either the only known way or offers the most efficient implementation. Recursive programming is also a prerequisite for the later tic-tac-toe strategy exercise.

Recursive programming uses methods calling themselves typically involving:

  1. A recursive expression reducing a problem from step n to n - 1 for 0 < n .

  2. A termination condition for n = 0 .

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) using only use recursion and termination conditions. Your implementation shall avoid any loop construct altogether.

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 even write: 

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

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

Prev  Up  Next
Factorial, the direct way  Home  Binomials, the recursive way