Factorials

Recursive computation of factorials

This example is a slight cliché, but it is still a good illustration of both the beauty and pitfalls of recursion.

The factorial of an integer, $n$, is the product of all the integers between $1$ and $n$. For example, six factorial (usually written $6!$) is:

$$6*5*4*3*2*1 = 720$$

Now, as we said in the introduction, the obvious way to do this is with a loop. But there is an alternative, “cleverer” way, using recursion.

We can make a simple observation that $6!$ is actually $6*5!$. And $5!$ is $5*4!$ and so on. So, we can calculate $n!$ without ever explicitly calculating a factorial at all. We just keep relying on smaller and smaller factorials without ever calculating them.

Of course, you must stop somewhere – we know that $1!$ is $1$.