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.

Â