Fraktal funksjoner

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\cdot 2\cdot 3\cdot 4\cdot 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\cdot (n-1)$‍ choices for the first two things, in order. Now, for each of these first two choices, we have $n-2$‍ choices for the third thing, giving us $n\cdot (n-1)\cdot (n-2)$‍ choices for the first three things, in order. And so on, until we get down to just two things remaining, and then just one thing remaining. Altogether, we have $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$‍ ways that we can order $n$‍ things. And that product is just $n!$‍ ($n$‍ factorial), but with the product written going from $n$‍ down to 1 rather than from 1 up to $n$‍.

Another use for the factorial function is to count how many ways you can choose things from a collection of things. For example, suppose you are going on a trip and you want to choose which T-shirts to take. Let's say that you own $n$‍ T-shirts but you have room to pack only $k$‍ of them. How many different ways can you choose $k$‍ T-shirts from a collection of $n$‍ T-shirts? The answer (which we won't try to justify here) turns out to be $n!/(k!\cdot (n-k)!)$‍. So the factorial function can be pretty useful. You can learn more about permutations and combinations here, but you don't need to understand them to implement a factorial algorithm.

The factorial function is defined for all positive integers, along with 0. What value should 0! have? It's the product of all integers greater than or equal to 1 and less than or equal to 0. But there are no such integers. Therefore, we define 0! to equal the identity for multiplication, which is 1. (Defining 0! = 1 meshes nicely with the formula for choosing $k$‍ things out of $n$‍ things. Suppose that we want to know how many ways there are to choose $n$‍ things out of $n$‍ things. That's easy, because there is only one way: choose all $n$‍ things. So now we know that, using our formula, $n!/(n!\cdot (n-n)!)$‍ should equal 1. But $(n-n)!$‍ is 0!, so now we know that $n!/(n!\cdot 0!)$‍ should equal 1. If we cancel out the $n!$‍ in both the numerator and denominator, we see that $1/(0!)$‍ should equal 1, and it does because 0! equals 1.)

So now we have a way to think about $n!$‍. It equals 1 when $n=0$‍, and it equals $1\cdot 2\cdots (n-1)\cdot n$‍ when $n$‍ is positive.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.