Recursive Algorithms - The Factorial Function

Although the factorial function \((n !)\) can be computed by a simple iterative algorithm, it is a good example of a function that can be computed by a simple recursive algorithm. As a reminder, for any positive integer n, factorial(n), written mathematically as n! is the product of all positive integers less than or equal to n. It is often defined by \(n !=n \cdot(n-1) \cdot(n-2) \cdot \ldots \cdot 2 \cdot 1\). The “…” is called an ellipsis. It is a way of avoiding writing what we really mean because it is impossible to write what we really mean, since the number of numbers between (n-2) and 2 depends on the value of n. The reader and the author both agree that the ellipsis means “and so on” without worrying about exactly what “and so on” really means. From the definition of n! we have:

and,

By substituting the left-hand side of the second equation into the right-hand side of the first, we get

This would be a circular definition if we did not create some kind of stopping condition for the application of the definition. In other words, if we needed to find the value of 10 !, we could expand it to 10 . 9! ! and then 10 . 9 . 8! and then 10 . 9 . 8 . 7! and so on, but if we do not define what 0! is, it will remain undefined. Hence, this circularity is removed by defining the base case, 0!=1.

The definition then becomes:

This is a recursive definition of the factorial function. It can be used to find the value of n! for any nonnegative number n, and it leads naturally to a recursive algorithm for computing n!, which is written in C below.

/*
Precondition: n >= 0
Postcondition: returns n!
*/
int factorial(int n) {
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

Observations

1. This does not result in an infinite sequence of calls because eventually the value passed to the argument of factorial is 0, if it is called with n >= 0, because if you “unwind” the recursion, you see each successive call is given an argument 1 less than the preceding call. When the argument is 0, it returns a 1, which is the base case and stops the recursion.
2. This function does not really compute n! because on any computer, the number of bits to hold an int is always finite, and for large enough n, the value of n! will exceed that largest storable integer. For example; 13! = 6,227,020,800 which is larger than the largest int storable on a 32-bit computer.

Short circuiting recursion

Short-circuiting the base case means that you check if the next call will be the base case instead of calling the function and then checking for the base case. It’s done to improve the efficiency of the algorithm by avoiding calling a function that will immediately return.

In the factorial function above, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function. The box shows C code to shortcut factorial cases 0 and 1.

static int fac2(int n) {
  // assert(n >= 2);
  if (n == 2)
    return 2;
  else
    return fac2(n - 1) * n;
}

int fac2wrapper(int n) {
  if (n <= 1)
    return 1;
  else
    return fac2(n);
}

At this point you may wonder, why do we care about doing all these checks just to avoid one function call? Short-circuiting is useful when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for O(n) algorithms, such as the depth first search algorithm.