The factorial function

For our first example of recursion, let's look at how to compute the factorial function. We indicate the factorial of $n$ by $n!$. It's just the product of the integers $1$ through $n$. For example, $5!$ equals $1⋅2⋅3⋅4⋅5$, or $120$. (Note: Wherever we're talking about the factorial function, all exclamation points refer to the factorial function and are not for emphasis.)

You might wonder why we would possibly care about the factorial function. It's very useful for when we're trying to count how many different orders there are for things or how many different ways we can combine things. For example, how many different ways can we arrange $n$ things? We have $n$ choices for the first thing. For each of these $n$ choices, we are left with $n-1$ choices for the second thing, so that we have $n⋅(n−1)$ ...