0:02

In this video, we're going to walk you through

Â the seven steps to figure out the algorithm that computes factorial.

Â The first step is to work an instance of the problem yourself.

Â So, let's begin by computing four factorial by hand.

Â The first thing we would do is recognize that

Â four factorial is defined as four times three factorial,

Â which now gives us the problem of solving three factorial.

Â Three factorial is defined as three times two factorial.

Â So we figure out what two factorial is.

Â It is defined as two times one factorial.

Â So, we figure out what one factorial is,

Â which is one time zero factorial and zero factorial is just one.

Â Now that we know what zero factorial is,

Â we can replace zero factorial with a one.

Â Now, we know what one factorial is,

Â one times one which equals one,

Â so we replace one factorial with one.

Â Two factorial is two times one which equals two,

Â so we replace two factorial with two.

Â Three factorial is three times two which equals six,

Â so we replace three factorial with six.

Â Four factorial is four times six which equals twenty four.

Â So, this is our answer to the whole problem.

Â In step two, we need to take a moment to

Â think about what we did in step one and write down the sequence of operations.

Â When we needed to figure out what four factorial was,

Â the first thing we did was compute three factorial.

Â When we needed to compute three factorial,

Â the first thing we did was compute two factorial.

Â For two factorial, we computed one factorial.

Â For one factorial, we needed to know what zero factorial was.

Â But for zero factorial,

Â we didn't need to compute anything.

Â We just knew that zero factorial has the value of one.

Â Once we figured out what the value of zero factorial was,

Â we used it to compute the value of one factorial by multiplying that by one.

Â Once we knew the value of one factorial,

Â we used it to compute two factorial by multiplying it by two.

Â Once we knew the value of two factorial,

Â we used it to compute three factorial by multiplying it by three.

Â Finally, we used the value of three factorial to

Â figure out the value of four factorial by multiplying it by four.

Â Let's take a minute to write down the steps we did for each of these computations.

Â To compute zero factorial,

Â we simply answered one.

Â To compute one factorial,

Â we computed zero factorial then we multiplied that result by one and that was our answer.

Â To compute two factorial,

Â we computed one factorial,

Â multiplied that result by two and that was our answer.

Â To compute three factorial,

Â we computed two factorial,

Â multiplied that result by three and that was our answer.

Â Finally, to compute four factorial,

Â we computed three factorial,

Â multiplied that result by four and that was our answer.

Â Step three is to generalize our process.

Â Let's take a moment to look over the computations we performed.

Â The first thing you might notice is that computing four factorial

Â down to one factorial involved very similar steps.

Â Whereas, computing zero factorial was a little bit different.

Â This is a special case called the base case,

Â and usually, it's incorporated into the definition of the thing we're trying to compute.

Â For example, part of the definition of factorial is that zero factorial equals one.

Â So, the first thing we might write down when trying to generalize

Â this process is recognizing the one case that's a little bit different.

Â We should determine if n is zero or not.

Â Then, the answer is just one.

Â Otherwise, we need to do something a little more complicated.

Â Let's look a little more closely at how we computed four factorial down to one factorial.

Â The first thing you might wonder is,

Â why are we computing three factorial to compute four factorial?

Â Also, why are we computing two factorial to compute three factorial?

Â In generalizing this, we'd realize that every time we compute n factorial,

Â we compute n minus one factorial,

Â which is the first step in the process.

Â We're going to compute n minus one factorial and we'll give it a name,

Â we might call it n minus one fact.

Â Now that we've figured out the pattern of behavior,

Â we can update our description below using this generalized description.

Â Every time we compute a particular factorial,

Â we compute n minus one factorial and then multiply that by some integer value.

Â So, let's take a closer look at that integer value.

Â When we compute four factorial,

Â we multiply n minus one fact by four.

Â When we compute three factorial,

Â we multiply n minus one fact by three.

Â The pattern that we see here is that the integer is always in.

Â So, we can generalize our steps to say that we are multiplying n minus one fact

Â by n. And that resulting product is the answer.

Â Now that we've written carefully generalized steps for calculating factorial,

Â it's important to take a minute to test our algorithm using a variety of possible inputs.

Â Try computing several test cases yourself.

Â Does it work? Testing a negative input values

Â is actually going to show us a flaw in our code.

Â Consider the calculation of negative two factorial.

Â Negative two is not equal to zero,

Â so we're going to recurse and compute negative three factorial.

Â Negative three is also not zero,

Â so we're going to compute negative four factorial, and so on.

Â You can see that this code is going to recurse

Â forever since it doesn't make progress towards the base case.

Â In fact, we have a mistake in our algorithm.

Â We need to be testing whether n is less than or equal to zero,

Â not just whether it is equal to zero.

Â Now, we've written out our algorithm and tested it,

Â even finding a bug in our algorithm.

Â In the next video, we will translate this algorithm to code.

Â