Iterative Fibonacci Function Example
⇐ Use this menu to view and help create subtitles for this video in many different languages. You'll probably want to hide YouTube's captions if using these subtitles.
Iterative Fibonacci Function Example : One way to write a Fibonacci function iteratively
- In the last video I challenged you to write
- multiple Fibonacci functions. The ones that could calculate
- the "n-th" 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 the is really multiple ways of even doing this
- So let's define our function "fibonacci" and it has a peremiter "n".
- That is what we are 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 are really going to do some,
- you know, some actual list manipulation in this video.
- So the terms here, the 0-th term of the fibonacci sequence is 0
- and the first one is 1.
- This is by definition. So we're just gonna kinda hardcode that in right there.
- And then what we're gonna do is, then we're going to construct this list
- to all of the terms up to and including the "n-th" term.
- And then return the "n-th" term from that list. And the reason
- why I'm going to do it this way is that it is able to save up
- kind of a memory of all the Fibonacci numbers, which is helpul
- for computing each incremental Fibonacci number. So let's do it this way.
- I'm gonna use the while-loop. You could do it using the for-loop but for me
- the while-loop feels a little more natural for this.
- And actually before I even define the while-loop, I'm gonna set my
- variable of iteration I should say. I'm gonna set that equal to 0.
- And your gonna see how this works in a second.
- So I'm gonna say while "i" is less than or equal to n, so "i" is
- gonna start at 0 and go up to n. And frankly I shouldn't start
- at 0. Cause we already have this 0-th term here on the first term here
- and we want to construct the second, third, fourth all the way
- to the n-th term. So actually let's start "i" at 2. So we
- already have the 0-th term in the first term, we then want to
- construct the second term so thats why we are going to start "i" equals 2
- all the way up to and including the n-th term.
- So that's why we say less than or equal to n, we are gonna
- keep adding terms to this sequence.
- So while "i" is less than or equal to "n", I'm gonna 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 could 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 at the end of the list is going to be
- the SUM of the previous 2 terms. So it is going to be
- terms "i" - 1, so thats the previous term, terms "i"-1 literally refers
- to the previous term plus terms "i" - 2. So it is essentially going to construct this Fibonacci
- sequence and build it in this list and then we are going to increment "i".
- I is equal to "i" + 1. If we never increment "i" then this loop
- will just keep going on for ever and ever but this way it's gonna keep going
- up and up until at some point "i" is not going to be less than or equal to "n"
- and then we are going to break out of the loop. And then
- when we break out of the loop, we can then return the "n-th"
- Fibonacci term in the sequence. So we're going to return the "n-th" term in terms.
- So let's see if this works, let's see if this makes sense.
- So I'm going to go all the way up to the n-th term.
- And actually the "n-th" term here, yes this should work cause if I had
- if this was Fibonacci of 0, I want it to return terms of 0 which is this term over here
- if it's Fibonacci of 1 I wanna return this term right over here.
- So it's the first term in terms over here not 0-th 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 gonna show you a little bit of example how these lists work.
- So if I define a list as, I don't know, 1,2. That's my list.
- And if i then say, it is doing something weird, so I'm gonna define my list as
- 1 coma 2
- So if i type "a" it is 1,2. If I append "a", a.append.
- Let's I append a 7 to it then if I look "a" I have a 7 at the end it.
- If I wanna refer to the elements here a should be the first element.
- The second element, i've just put 2 in the bracket, should give me the 7.
- So that is exactly what I'm doing over here.
- I'm saying terms of "i" - 1, so we're going to add a new term over here
- so this first time we go through the loop we are going to add a new term
- and it is going to be the SUM of terms of "i" - 1, so in that first loop "i" is 2
- "i" - 1 is 1 so terms of 1 + terms of 0.
- So it is going to be terms of 1 which is + terms of 0.
- And then it keeps doing that all the way until we construct the n-th term.
- Well enough talk and I'll step through it a little bit clearer in the next video
- with the particular example but let's just see what we wrote
- actually works. So let me run it.
- All right.
- Let's see if we get the proper results.
- Well let's just start at the beginning.
- Fibonacci of 0 well that looks good.
- Let's try Fibonacci of 1.
- That looks good.
- Fibonacci of 2 that should also be 1.
- That looks good.
- Fibonacci of 3 this should be 2 now cause we are taking the SUM of 1 + 1.
- That works.
- Let's try the Ficonacci of 10.
- Hey that looks pretty good.
- Let's try the Fibonacci of something huge.
- Fibonacci of a 100.
- This is a very large number and I'm not going to go into the whole
- floating kind of the long numbers and super long large ones but let's try
- something a little bit smaller over here.
- So let's try Fibonacci of 20.
- So it looks like it works and you can verify for yourself.
- So this is just one implementation of it and in the next few I'm gonna try
- another way to implement it. Maybe I'll do it with a for-loop or we could also do it recursively.