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.