# 3.6.A Recursive factorials

- Page ID
- 10078

A simple example of a recursive subroutine is a function that computes *n*! for a nonnegative integer *n*. *n*!, which is read “*n *factorial”, is defined as follows:

\(0 !=1\)

\(n !=\prod_{i=1}^{n} i \qquad\) for \(n>0\)

For example, 5! = 1 · 2 · 3 · 4 · 5 = 120. Note that for *n *> 1,

\(n !=\prod_{i=1}^{n} i=\left(\prod_{i=1}^{n-1} i\right) \cdot n=((n-1) !) \cdot n\)

It is also true that *n*! = ((*n *− 1)!) · *n *when *n *= 1. This observation makes it possible to write a recursive function to compute *n*!.

All the programming examples in this section are written in the Java programming language. I won’t put these blue boxes around them.

To compute *factorial*(*n*) for *n *> 0, we can write a function (in Java). This function computes factorial(*n *− 1) first by calling itself recursively. The answer from that computation is then multiplied by *n *to give the value of *n*!. The recursion has a base case, namely the case when *n *= 0. For the base case, the answer is computed directly rather than by using recursion. The base case prevents the recursion from continuing forever, in an infinite chain of recursive calls.

Now, as it happens, recursion is not the best way to compute *n*!. It can be computed more efficiently using a loop. Furthermore, except for small values of *n*, the value of *n*! is outside the range of numbers that can be represented as 32-bit ints. However, ignoring these problems, the factorial function provides a first example of the interplay between recursion and induction. We can use induction to prove that factorial(*n*) does indeed compute *n*! for *n *≥ 0.

Theorem 3.11.

*Assume that the data type int can represent arbitrarily large integers. Under this assumption, the factorial function defined above correctly computes n! for any natural number n.*

*Proof*. Let *P*(*n*) be the statement “factorial(*n*) correctly computes *n*!”. We use induction to prove that *P*(*n*) is true for all natural numbers *n*.

Base case: In the case *n *= 0, the if statement in the function assigns the value 1 to the answer. Since 1 is the correct value of 0!, factorial(0) correctly computes 0!.

Inductive case: Let *k *be an arbitrary natural number, and assume that *P*(*k*) is true. From this assumption, we must show that *P*(*k *+ 1) is true. The assumption is that *factorial*(*k*) correctly computes *k*!, and we want to show that factorial(*k *+ 1) correctly computes (*k *+ 1)!.

When the function computes factorial(*k *+ 1), the value of the parameter *n *is *k *+ 1. Since *k *+ 1 > 0, the if statement in the function computes the value of factorial(*k *+ 1) by applying the computation factorial(*k*) ∗ (*k *+ 1). We know, by the induction hypo- thesis, that the value computed by factorial(*k*) is *k*!. It follows that the value computed by *factorial*(*k*+1) is (*k*!)·(*k*+1). As we observed above, for any *k*+1 > 0,(*k*!)·(*k*+1) = (*k *+ 1)!. We see that factorial(*k *+ 1) correctly computes (*k *+ 1)!. This completes the induction.

In this proof, we see that the base case of the induction corresponds to the base case of the recursion, while the inductive case corresponds to a recursive subroutine call. A recursive subroutine call, like the inductive case of an induction, reduces a problem to a ‘simpler’ or ‘smaller’ problem, which is closer to the base case.