Stepping Through Iterative Fibonacci Function

⇐ 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.

Stepping Through Iterative Fibonacci Function : Understanding how the iterative fibonacci function works for a particular example

相關課程

0 / 750

So we can make sure we really understand what's happening in this little iterative fibonacci fuction
I am going to step through it with a particular example
So we are going to assume that this function is called with the argument 5.
So we want the 5th term in the fibonacci sequance.
Starting at where indexing thing starting at 0.
So the 0th term will be the... really... sometimes you would imagine the 1st term to be.
Will start with the 0th term.
So we're assuming that fibonacci of 5 is called.
So we want the 5th term. Starting at the 0th term, so we want 5th one.
And so when we go into this program terms starts... is defined as this list right here.
That has just 2 elements: 0 and 1.
So what I've done here is: I'm going really to focus what happens in this loop
so as we enter into this loop the first time that we entered to this loop
terms is refering to a list that has just 0 and 1 in it.
And we did that because by definition those are the first two terms of the fibonacci sequence
and then also entering into in the loop we defined i as beeing equal to... i as beeing equal to 2
and we do that because we've already defined the 0th term and the 1st term
and so now we want to as we enter the loop... start... we want to add...
we want to add the second term as we go into the loop
and then we say while i is less than or equal to n.
Well we already know that n is 5.
So in the scope of this function while we are running it, the variable n is 5.
And so clearly i is still less than or equal to 5 so we will run this code right over here
and we are appending to terms so we are going to append something.
So entering into this clause is what i in terms would look like.
But looks like we are going to append something to terms so terms is going to look like...
Terms is going to be 0 and 1 and there we are going to add something...
We are going to add something right over here to terms
and what is that thing we are going to add?
We are going to add whatever this bussiness over here is.
It seems complicated, but when you break it down it doesn't look too bad.
In this situation what is i minus 1?
Well i is 2 so in this situation i minus 1 is going to be 1 and i minus 2 is going to be 0
as we go trough this interation.
So terms... the first term in terms... the first terms is the 0th term.
This is the first term.
So the first term in terms is literally a 1.
So this whole thing is 1 and the 0th term in terms.
Remember, terms... the 0th term in terms.
Acctually I should write this way.
0th term in the... the list is called terms.
0th term in terms. This is what term looks like right now and it's going to be 0.
So this whole thing is going to be 0 as well.
So it's 1 plus 0 which is 1 and that's what we are appending to terms.
So we are going to append a 1 over here and then we say i is equal to i plus 1.
Well i is now equal to 2 so you are going to add 2 plus 1 is 3 and that's going to be the new value.
The new value for i.
And then we go back. We loop back up to the beginning of the while loop
and we say while i is less than or equal to n.
Well now i is a little bit closer to n. It's 3 now, but it's still less than or equal to 5.
So now evaluate this again.
Once again entering into the loop.
Terms now looks like this: 0, 1, 1.
i looks like this, 3.
It's really what the same values we had exiting the loop
and now we evaluate right over here.
We are going to add something to terms.
So terms right now: 0, 1, 1 we are going to add something to it.
What is that something?
It's going to be the i minus 1 term of terms.
So what's the i?
I over here is 3. 3 minus 1 is 2.
So this right over here is now going to be 2.
So it's going to be the second indexed term in terms so this is the 0th, the 1st the 2nd.
So this over here is going to evaluate to 1 plus i minus 2.
Well i is now 3. 3 minus 2 is 1. So plus the first term in terms.
So this is the 0th term in the 1st term so this is also going to be a 1 over here.
So it's going to be 1 plus 1 or 2.
So we are going to append a 2 to terms.
So that's what this does over here and then we take whatever i was
which is i in this iteration is 3. We are going to add 1 to it and redefine i to be that.
So 3 plus 1 is 4 and that's the new i.
Then we go again to the beginning of the loop while i is less than or equal to n.
While i is now 4, n is always, still 5.
4 is less than or equal to 5 so we run this again
and once again we need to figure out what terms of i minus 1 are.
Let me write it over here. This is getting kinda messy.
Maybe i should clear this up. Cuz i wanna you to be able to read it clearly.
So let me clear this.
So now in this loop.
Let's just think about what... so now... Let me write it over here.
Entering the loop, now i is equal to 4.
I'm going to do that in the same orange colour.
Entering into the loop i is equal to 4 and the terms...
Terms has now been... It now has 4 elements in this: 0, 1, 1 and 2.
And now 4 is still less than or equal to 5 so we do this
and we have to figure out what terms of i minus 1 is.
Well now i minus 1 is 3. Right?
4 minus 1 is 3 so terms of... well the 3rd elem...
not terms of. I should say the 3rd element in terms is: 0, 1, 2, 3.
So it's going to be this whole thing.
It's going to be this 2 right over here.
So we are going to take that 2. I know you can read that.
We are going to take this 2...
This 2 and we are going to add it to terms, the i minus 2th terms.
I is 4. 4 minus 2 is 2. The 2nd term in terms is 0, 1, 2.
It's a 1.
It's this one right over here.
So we are adding this 2 plus this 1 to now get 3 and we are taking...
So this whole thing... when you added 3 and we are appending it to terms.
So terms was: 0, 1, 1, 2, but now we are appending a 3 to the end of it
and then we are saying i is equal to i plus 1.
I was 4. 4 plus 1 is 5 so that is what i is equal to now.
It's equal to 5.
Then we go to the beginning of the loop.
I is now going to be equal to 5. Terms.
Let me write that in the same colour for consistency.
Terms are now: 0, 1, 1, 2 and 3 and then we say while i is less than or equal to n.
N is 5. Well 5 is still less than or equal to 5.
It's equal to 5 so this still is true so we'll execute this clause
and now we have to figure out...
Let me clear this out again.
Now we have to figure out what is terms of i... what is the i minus 1'th term in terms.
So now i is 5. so it's 5 minus 1. So it's the 4th term in terms.
So 0, 1, 2, 3, 4. So it is this term right over here. It is the 3.
So this over here is 3 now and then we have... and then we have to think about...
Let me do this in another colour.
Then we have i minus 2. I is 5 now. 5 minus 2 is 3. the 3rd term in terms: 0, 1, 2, 3 is this over here.
So this over here is 2.
So you evaluate this. You'll notice, we are just adding the last 2 terms that we had so far.
This is how we build our fibonacci sequance
and so 3 plus 2 is 5 so we are going to append a 5 to the end of terms.
So terms is going to be: 0, 1, 1, 2, 3 and then we are going to append...
We are going to append a 5 to it and then we say i is equal to i plus 1.
So i is equal to 5 plus 1 or 6. I is equal to 6 now.
When we go to the beginning of the loop and it says
while i is less than or equal to n.
Well now i is 6 and n is... has been 5. 6 is not less than or equal to 5 so this is false.
So we do not... We break out of the loop and we go to...
I guess we stopped running it and then we go to return...
return the nth term in terms. So remember. N was 5.
So what's the 5th term. If we started 0.
So this is the 0th term, 1st term, 2nd term, 3rd term, 4th term, 5th term.
And we are done.
And hopefully that gives you and understanding of why this works and also a little bit of the logic
of how we wrote it.
It's literally building up the fibonacci sequence so the way you would expect to.
It started with the first 2 terms by definition and then each time we went to the loop
and added another term it said hey, the new term is going to be the sum of the last term right now
and the second to last term and add them together and that will be the new term
and you keep doing that until you have essentially... until you have added that nth term.

留言:

載入中...

新增一則留言(尚未登入)

stepping through iterative fibonacci function 討論區:

載入中...