MIT 6.00 Intro Computer Science (OCW) OpenStudy (anonymous):

hi, i understand how fibonacci number works but i don't understand the coding part of it. can someone please explain it to me? OpenStudy (anonymous):

Do you mean you need help with how to build the function, or you're looking at the function on a handout and you need help figuring out what it does? OpenStudy (anonymous):

i'm looking at the function but can't figure out what it does OpenStudy (anonymous):

This one? def fib(x): """Return fibonacci of x, where x is a non-negative int""" if x == 0 or x == 1: return 1 else: return fib(x-1) + fib(x-2) OpenStudy (anonymous):

yes OpenStudy (anonymous):

well, the first part is easy. the line: if x == 0 or x == 1: return 1 checks to see if x is 0 or 1 if x isn't 0 or 1, the next line returns fib(x-1) + fib(x-2) fib(x-1) is going to go through the same process. If (x-1) is greater than 1, THAT will also get sent to fib. But eventually fib(x-1) will return an integer. When it does, the program will start to evaluate fib(x-2) the same way. when fib(x-2) returns an integer, the problem becomes simple addition. OpenStudy (anonymous):

when you say "If (x-1) is greater than 1, THAT will also get sent to fib" does that mean the function will go through fib(x-1) then fib((x-1)-1 then fib(((x-1)-1)-1) and so on also when will fib(x-1) return an integer? i thought fib(x-1) will always be an integer OpenStudy (anonymous):

when you say "If (x-1) is greater than 1, THAT will also get sent to fib" does that mean the function will go through fib(x-1) then fib((x-1)-1 then fib(((x-1)-1)-1) and so on Exactly, UNTIL one of those (x-an accumulating number of ones) terms is in the base case, that is, when the line that says if x == 0 or x == 1: return 1 is true, the function will stop calling fib(x-whatever) and will just return 1 also when will fib(x-1) return an integer? i thought fib(x-1) will always be an integer Instead of fib(x-1) think of it as 'the integer that gets returned when fib(x-1) is finished being evaluated' So it is an integer, but it takes some time (the time to evauate fib(x-1)) to figutre out what the integer is. OpenStudy (anonymous):

One way to see this is to consider x = 2. Since x is not 1, the function computes fib(1) + fib(0). But those two values are known to be 1, so the answer is 1+1 = 2. Now consider x = 3. Since x is not 1, the function computes fib(2) + fib(1). fib(2) expands to fib(1) + fib(0), so the answer is 1+1+1 = 3. And so on. OpenStudy (anonymous):

thanks! i think i got so lets say x = 4 fib(4) = fib(3) + fib(2) = [fib(2) + fib(1)] + [fib(1) + fib(0)] =[fib(1) + fib(0) + fib(1)] + [fib(1) + fib(0)] OpenStudy (anonymous):

Exactly. Well done.

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Latest Questions Blueberryboy: what is the slope of this graph?
1 hour ago 4 Replies 1 Medal SamRoman: #20. A debit takes money out of your account True or False #21. A credit adds money to your account True or False #22.
1 hour ago 18 Replies 1 Medal bunnyishere: A 10-meter cable is stretched from the top of a pole to an anchor on the ground. It is anchored on the ground 4 meters away from the base of the pole.
32 minutes ago 1 Reply 0 Medals SamRoman: If you have overdraft protection and you don't have enough money for a transaction, it will process anyway.
2 hours ago 8 Replies 0 Medals SamRoman: If a check has cleared it will not be on your bank statement? True or False
2 hours ago 6 Replies 0 Medals PoseidonGodOfTheSea: A plant species has two possible gene variations for seed shape: smooth and wrinkled.
3 hours ago 6 Replies 0 Medals taylahodo: what was the reason why Kalief Browder died and got a accused?
4 hours ago 5 Replies 0 Medals lanyiah85: Brian, Steve, and Rita invested a total of \$24,000 in a business. Each person invested the same amount.
4 hours ago 3 Replies 1 Medal kekeman: Help please: https://snipboard.io/i2JBGZ.jpg
3 minutes ago 21 Replies 1 Medal kekeman: Help: https://snipboard.io/QBXPjO.jpg
3 hours ago 5 Replies 0 Medals
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!