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.