In the last video I challenged you to write multiple Fibonacci
functions, ones that could calculate the nth
term of the Fibonacci sequence either iteratively
or recursively.
And I'll do the first shot right over here.
And I'll show you over the next few videos
that there's really multiple ways of even doing this just
iteratively.
So let's define our function, Fibonacci.
And it has a parameter n, so that
is what we're going to pass to the function.
And we know that by definition, the first two
terms of the Fibonacci sequence are 0 and 1.
So let's make a list for ourselves.
And so this is interesting.
So this is the first time we're really
going to do some of the actual list
manipulation in this video.
So the terms here-- the 0th term of the Fibonacci sequence is 0.
And the first 1 is 1.
This is by definition.
So we're just going to kind of hard code that in right there.
And then what we're going to do is
if we're then going to construct this list to all
of the terms up to and including the nth term,
and then return the nth term from that list.
And the reason why I'm going to do it this way
is it's able to save up kind of a memory of all the Fibonacci
numbers, which is helpful for computing
each incremental Fibonacci number.
So let's do it this way.
I'm going to use a while loop.
You could do it using a for loop,
but for me a while loop feels a little bit more natural
for this.
And actually before I even define the while loop,
I'm going to set my variable of iteration.
I'm going to set that equal to 0,
and you're going to see how this works in a second.
So I'm going to say while i is less than or equal to n.
So i is going to start at 0, and then go up to n.
And actually frankly, i shouldn't start at 0
because we already have the 0th term here and the first term
here.
And we want to construct the second, third, fourth,
all the way to the nth term.
So actually, let's start i at 2.
So we already have the 0th term and the first term.
We then want to construct the second term.
So that's why we're going to start i equals 2,
all the way up to and including the nth term.
So that's why we say less than or equal to n.
We're going to keep adding terms to this sequence.
So while i is less than or equal to n,
I'm going to take this list right here, and to the end
of that list-- and this is a built-in function
for any list in Python, and you're learning it now.
And you can look it up, and actually my IDE
tells me how to use it-- I can add to the end of that list
another term.
And that next term I'm going to add to the end of the list
is going to be the sum of the previous two terms.
So it's going to be, terms i minus 1.
So that's the previous term.
Terms i minus 1 literally refers to the previous term.
i minus 1 plus terms i minus 2.
So this is essentially going to construct this Fibonacci
sequence and build it in this list.
And then we're going to increment i.
i is equal to i plus 1.
If we never increment i, then this loop
will just keep going on forever and ever.
But this way it's going to keep going up
and up and up until at some point i
is not going to be less than or equal to n,
and then we're going to break out of the loop.
And then when we break out of the loop--
let me do it right over-- when we break out of the loop,
we can then return the nth Fibonacci term in the sequence.
So we're going to return terms.
We're going to return the nth term in terms.
So let's see if this works.
Let's see, does this make sense?
So I'm going to go all the way up to the nth term,
and actually the nth term here-- yes, this should work.
Because if this was Fibonacci of 0,
I want to return terms of 0, which is this term right here.
If it's Fibonacci of 1, I would want
to return this term right over here.
So the first term in terms.
Not the 0th, but the first.
So this feels like it should work.
And actually even before I run it,
I want you to make sure you understand
what I've done here with the list.
So I'm going to show you a little bit an example of how
these lists work.
So if I define a list as, I don't know, 1 comma 2.
That's my list.
And if I then say-- it's doing something weird.
So I'm going to define my list as 1 comma 2.
So if I type a, it's 1 comma 2.
If I append to a, a dot append.
So if I append a, let's say I append a 7 to it.
Then if I look at a, I have a 7 at the end of it.
If I want to refer to the elements here, a of 0
should be the first element.
a, the second element, I just put the 2 in the brackets
and it should give me the 7.
So that's exactly what I'm doing over here.
I'm saying terms of i minus 1.
So we're going to add a new term over here.
So this first time it goes to loop,
we're going to add a new term.
And it's going to be the sum of terms of i minus 1.
So in that first loop, i is 2. i minus 1 is 1.
So terms of 1 plus terms of 0.
So it's going to be terms of 1 which is 1, plus terms of 0.
And then it keeps doing that all the way until we
construct the nth term.
Well enough talk, and I'll step through it a little bit clearer
in the next video with a particular example.
But let's just see if what we wrote actually works.
So let me run it.
All right.
And let's see if we get the proper results Fibonacci--
well, let's just start from the beginning-- Fibonacci of 0.
Well, that looks good.
Let's try Fibonacci of 1.
That looks good.
Fibonacci of 2.
This should also be 1.
That looks good.
Fibonacci of 3-- this should be 2 now,
because we're seeking the sum of 1 plus 1.
That works.
Let's try the Fibonacci of 10.
Hey, that looks pretty good.
Let's try the Fibonacci of something huge.
Fibonacci of 100.
Well, this gets a little bit-- I won't go into the-- well,
this is a very large number, and I'm not
going to go into the whole floating
kind of the long numbers and the super large ones.
But let's try something a little bit smaller here.
So let's try Fibonacci of 20.
So it looks like it works, and you can verify it for yourself.
So this is just one implementation of it,
and in the next few videos, I'm going
to try another way to implement it.
Maybe I'll do it with a for loop,
or we can also do it recursively.