0:03

In this video, we're going to walk through the first four steps of

the programming process in the context of Fibonacci.

We'll begin by working out an example computing Fibonacci of four.

Fibonacci of four is defined as Fibonacci of three plus Fibonacci of two.

So what's Fibonacci of three?

It's defined as Fibonacci of two plus Fibonacci of one.

What about fib two?

That's defined as fib one plus fib zero.

And fib one and fib zero are defined as one and zero, respectively.

So, one plus zero gives one.

Now, we need to move over to the right hand side of the blue expression,

calculating Fibonacci of one, which,

as we just said, is one.

So now, we add one plus one and get two.

Since we have now computed fib three,

we move over to the right hand side of the top expression computing Fibonacci of two.

Fib two is defined as fib one plus fib zero.

And as we said earlier,

fib one and fib zero have the values one and zero, respectively.

If we add those together, we get one.

So, fib four has the value of two plus one,

or three, and that's our answer.

In step two, we need to write down all of

the things we did in step one to compute fib four.

So, let's begin with the tree we just created and

write down all the steps we performed along the way.

First, we computed fib three.

This prompted us to compute fib two.

And in the process of computing fib two,

we had to compute fib one and fib zero.

Then we went back up to the blue expression and computed fib one.

Then we needed to move over to the right-hand side and compute fib two,

which required us to compute fib one and fib zero.

Let's take a look at how we compute Fibonacci of each of these numbers.

To compute fib zero,

we simply answered zero.

To compute fib one, we simply answered one.

To compute fib two,

we were required to compute fib one and fib zero and add them together.

For fib three, we computed fib two and fib one and added those together.

And for fib four,

we computed fib three and fib two and added those together.

Step three requires that we generalize,

looking for patterns in our series of steps.

The first thing you may realize is that computing fib four, fib three,

and fib two looks like a very similar set of steps,

whereas computing fib one and fib zero looks a little bit different.

In fact, computing fib one and fib zero are special cases called base cases,

we simply know the answer.

So what we might want to do is determine if n has the value of one.

And if it does, we just answer one.

Similarly, we determine if n has the value of zero.

And if so, answer is zero.

Otherwise, we're going to have to deal with

these complicated cases over here on the left.

So, let's look at that a little closer now.

The first thing you might want to do is

look at the first line of each of these computations.

Why is it that when we are computing fib four,

we began by computing fib three?

And why is it that when we computed fib three,

we had to compute fib two?

The general form here is that the first step for

computing fib n is to first compute fib n minus one.

So, we can replace this first line in each of these computations with,

compute fib n minus one,

which we will call, fib_n_minus1.

We can replace this line in each of our similar steps below.

Next, you might ask,

"Why were we computing fib two here,

and why were we computing fib one here?"

The general form is that the second step for computing

Fibonacci of n is to compute Fibonacci of n minus two.

The general form has as compute fib n minus two,

and we're going to call that fib_n_minus2.

We can replace that in the computation below.

And finally, we sum up our answers.

The great thing about creating a general form is that, now,

all of our steps for each of these calculations are identical.

And so, our otherwise case is simply these three steps regardless of whether n is two,

three, four or more.

In step four, it's important to test our algorithm.

Let's see if our algorithm works to compute Fibonacci of six or Fibonacci of one.

How about Fibonacci of negative two?

When we perform the test to see whether

Fibonacci of negative two is correctly calculated,

we're going to discover a problem.

Minus two is not equal to zero or one.

So we're going to step into our otherwise clause,

computing Fibonacci of minus three and Fibonacci of minus four and adding these together.

However, in order to compute fib negative three,

we're going to find ourselves computing fib negative four,

and fib negative five.

This process is not going to terminate.

This is not good. This test case portrays a problem in our algorithm.

In fact, we haven't been completely true to our definition of Fibonacci.

If you look back at the original definition of Fibonacci,

you can see that there are five cases,

the case where n is zero,

the case where n is one,

the case where n is greater than one,

and there's two cases where n is negative.

We didn't handle these two cases, and we need to.

The other thing to notice is that our otherwise clause was handling the case

where n is greater than one even though we never explicitly said so.

So, we're going to have to explicitly place that into our code,

testing whether n is greater than one.

And if it is, we perform those computations.

Otherwise, if n is less than zero,

we're going to need a few new steps.

Now, normally, we would suggest you go back and do

steps one to three to handle the additional Fibonacci cases.

For the sake of time, however,

let's assume we already did that,

and this is what we came up with.

If n is less than zero,

we're going to compute fib of minus n and call it fib_neg_n.

Then, when n is odd, that's the answer.

And when n is even,

we multiply fib of minus n by negative one, and that's our answer.

We would now test the revised algorithm with the new test cases.