0:02

Previously, we devised this algorithm to compute the nth Fibonacci number.

Â Now, let's turn that algorithm into code.

Â I've written those steps as comments and put the function declaration around them.

Â First, we determine if n is one,

Â which is now our familiar if/else statement.

Â Inside the then clause,

Â we give an answer, which is again familiar.

Â We will return that answer.

Â Inside the else clause,

Â we again compare n to a value and return an answer,

Â which will be similar to what we just did,

Â an if statement with a return statement inside of it.

Â We're just going to move this up to make a little more space

Â and see now that we need to make another decision.

Â So, we're going to have another if statement.

Â Inside of the then clause of this if statement is where things get interesting.

Â We want to name a quantity so we want to declare a variable.

Â But what value are we going to assign to it?

Â Computing fib of n minus one seems like a complicated step.

Â We've seen complicated steps before where we

Â have abstracted the complexity out into a function.

Â What would this function look like?

Â Well, it would take an int,

Â compute the Fibonacci of that int, and return it.

Â That sounds exactly like the function we're writing right now.

Â So instead of making a new function,

Â let's just call the Fib function we're currently writing.

Â This next step in the algorithm is quite similar.

Â We are going to call the Fib function to do

Â all the complicated work of computing fib of and n minus two.

Â Our next step calls for us to sum two variables and return them as our answer.

Â So, we can write a return statement for that.

Â Now, we'll just move the code up a little bit more and begin working on this else clause.

Â We have another if statement which we are just going to write with the else for brevity.

Â We are again declaring a variable and want to

Â initialize it with the result of a complicated step,

Â where we compute fib of negative n. So,

Â as before, we'll just trust the Fib function we are writing to do that work for us.

Â We're almost done, one more if/else statement.

Â Here, we are going to use mod to see if a number is even or odd.

Â Remember that n mod two will give us the remainder when we divide n by two.

Â So, zero will mean that n is even and one will mean the n is odd.

Â Inside the then clause,

Â we give our answer.

Â We were a bit imprecise saying that is our answer here.

Â Oops, what did we mean?

Â We meant fib neg n is our answer.

Â Likewise, in the else clause,

Â we want fib neg n times negative one to be our answer.

Â We've removed all the comments that we had so that we just have code.

Â Now, we might want to clean it up a little bit and make it look a little bit nicer.

Â The variables are a little bit cluttered.

Â We were verbose in our steps and separated out each computation giving it

Â a name but we might just return fib n minus one plus fib n minus two.

Â Likewise, instead of writing negative one times fib neg n,

Â we might just write negative fib neg n. These cases are exhaustive.

Â We have checked if and is one, zero,

Â and greater than one,

Â so the only other possibility by the time we get here is less than zero.

Â We can and should get rid of this extra if.

Â In fact, if we don't,

Â the compiler may complain that we could reach

Â the end of the function without returning a value.

Â Most compilers are not smart enough to reason about algebraic properties of

Â numbers and figure out if a set of conditions cover every possible case.

Â They do, however, understand that code will always execute

Â either the then clause or the else clause of an if/else.

Â We can also simplify these first few steps by realizing that if n is zero or n is one,

Â we're just returning n,

Â and write one if statement with an or in its conditional expression.

Â We could add a comment here to help the reader

Â understand what we were thinking. And then we're done.

Â Most of that cleanup was optional since

Â these two pieces of code are algorithmically equivalent.

Â However, this code looks much nicer than the code we started with.

Â