
So here's a way to define Fibonacci iteratively.

[BLANK_AUDIO]

We're going to avoid all the redundant computation by keeping track as we

go. And we're going to have two variables. And I'm going to do this

in a slightly strange way, and the reason for this will become

clear soon. I want to make it so we can get the right

answer when n is 0 and when n is 1, without having

special cases. So instead of keeping track of the previous two, I'm

going to keep track of the current one and the imaginary one that's

going to be after that. And we know that the first two Fibonacci

numbers are 0 and 1, so we'll use current is

0, and the next one, we'll call after is 1.

So that's the one after the one that we're currently

doing, and now we have a loop, so we're going to

go from i in the range from 0 to n.

So we're looking for Fibonacci number n, that means we

want to start at 0. The current value is the value

for Fibonacci 0 and after is the value for Fibonacci

1, and as we go through the loop, we'll keep

updating those. And we want to update them by following the

recursive rule and so that means that the new value

of current, is the current value of after. And the new

value of after, is the sum of those two lists;

current plus after. We can do that with a multiple

assignment, that'll save us from needing a temporary variable. We

can assign current and after, to their new values. The new

value of current, is the current value of after, and the

new value of after is current plus after. So, this is

the place where a multiple assignment comes in handy. If we

didn't use a multiple assignment, we'd have to use a temporary

value to keep track of one of these while we do

the assignments. But with multiple assignment, we get both of these

values first, and then we assign them to the two variables

on the left side. So, that's all we need. And then

after the loop, we should return the value of

current, which is the current Fibonacci number if we're looking

for Fibonacci N. So let's try that. So we

should be able to see Fibonacci 0, and the result

should be 0. And that's what we get, and,

because that's the value of current, when the range is

from 0 to 0, we don't go through the loop

at all. So we get the value 1. Let's check

Fibonacci 1, and we run this, we get the value 1, which is also

what we expect. And we got that because we went through the loop once, assigning

the value of after, which started as 1 to current and that's what we

return as the value of current. And we can keep going, we'll try Fibonacci 2.

And that's also 1, as we expect and Fibonacci 3

should be 1 plus 1, gets us 2 and so forth.

[BLANK_AUDIO].

Okay, so this looks like it's working. We've tried

a few simple ones. Let's try Fibonacci 33. So

we estimated in the earlier quiz, in order to

compute fibonacci 36, we would need Fibonacci 33 calls,

using the previous recursive definition. So, why did it

take so long for that code to run? So

what's the value of Fibonacci 33? And that's what

it is, it's 3 and a half million calls.

And so even with a processor that's doing a billion instructions

a second, doing 3 and a half million recursive calls takes

quite a while. Each time through the call, is many more

than just one instruction it's many thousands of instructions. So this

starts to take enough time that we didn't see the result.

And, it wasn't only those Fibonacci 33 calls to Fibonacci 2,

we had all the other things that we had to do

to get Fibonacci 36. But let's see that now we have

our faster, internet definition of Fibonacci that isn't doing all that duplicate

work, that we can compute Fibonacci 36. And so that gives us this value,

so indicating that there would be about 15 million rabbits after 3 years

using Fibonacci's model. Let's try what we'd have after 5

years, passing in 60 months, and we

get this starting to be quite a huge

number. To try to relate to this, let's look

at how long it would take for the mass

of all the rabbits that are born to exceed

the mass of the Earth. So the mass of the Earth is 5.9722 times 10 to the 24,

and that's in kilograms, and I'm using the times

time notation. This gives us a power, so this

is 10 to the power 24. So that's one way to write 5.9 times 10 to the 24

kilograms, just to demonstrate the power notation, this is

2 to the power 10, so we'll see the result

is 1,024. That's what we get by multiplying 2

times 2 times 2 times 2 10 times. Here we're

multiplying 10 by itself 24 times and that's a good

estimate for the mass of the earth. So now to

find out how many months it takes before the

mass of the rabbits exceeds the mass of the earth,

we're going to have a for loop. We're going to loop from

Fibonacci numbers, until we get to a number that exceeds

the mass of the Earth. We also need to decide what a mass of a rabbit is, and

I'm going to assume that a rabbit weighs about 2

kilograms. And, that's a pretty good guess for how heavy

a rabbit is. That's assuming of course, a well

fed rabbit like we have today, not if the rabbits

spread as fast as Fibonacci's model would suggest that

they do. So, we'll write a loop to see when

the mass of the rabbits exceeds the mass

of the earth. We'll start with n equals 1,

and we're going to keep going until Fibonacci n

exceeds the mass of the earth. So, we'll go

while Fibonacci n times the mass of the

rabbit. So Fibonacci n gives us the numbers of

the rabbits in month end, times the mass of

the rabbit and as long as that is less

than the mass of the Earth, the Earth is

still safe for humanity, or at least there's some space

left for humans. And every time through the loop,

we'll increase n by 1. And at the end of

the loop, we'll print out the value of n,

we'll see where we got, and let's also print out

the value of Fibonacci n, to see how big the

Fibonacci number of that n is. So we'll keep going

through the loop, as long as the Fibonacci of n times

the mass of the rabbit is less than the mass of the

Earth. And once we stop the loop that means we've exceeded

the mass of the Earth and we'll see what the results is.

So let's try running that, and, we get this result. The

value of n is 119, so it'll only take 119 months, or

just less than 10 years, until the mass of the rabbits exceeds

the mass of the Earth. And this is the number of rabbits

we would have then. A pretty big number, you should

be very afraid of all these rabbits. The good news

is that Fibonacci's model, is not actually correct. That this

was a mathematical abstraction for

rabbit reproduction. Real rabbits actually die

off after some point, and if there're too many rabbits,

they don't have enough food, so they don't keep growing

like the Fibonacci numbers and take over the entire planet.

So we should be very afraid if Fibonacci's model is correct.

It would only take 10 years for the rabbits to take over the entire planet,

and weigh more than the earth does itself. The good news is, it's not a very

accurate model of how rabbits reproduce, that

they don't live forever, and once there're too

many rabbits, they start to run out of

food. So they stop reproducing, and stop surviving.