Question

Hi there! Is Fibonacci code from lecture 4 correct?

Answer 1

Can't remember which lecture mentioned it, but it's discussed in several of the readings as well. I think that the readings explain it in more detail than the lecture did. I know that I found 4 or 5 codes for the fibonacci sequence in the readings, and I tested them all out in python so I could understand the differences.

Do you have a specific question about it?

Answer 2

did you try it?

looks like it works to me
http://pastebin.com/N1njStWJ

Answer 3

It could have assert stmts for if x <0 or if x is not an integer, but that's pretty nitpicky for a quick example problem. Looks good to me.

Answer 4

If you type fib(2), you actually don't get the value of fib(2), but fib(3) which is 2. fib(2)=1.
fib(2)=fib(1)+fib(0)=1+0=1
So, prof. Grimson gives the example of fib(12)=233, but it is indeed 144.
I changed the function to:

def fib(x):
if x == 0 or x == 1 or x == 2:
return 1
return fib(x-1) + fib(x-2)

Do you agree? Correct-me if I'm wrong. Thank you for your help!

Answer 5

I don't think you are correct, sleepl.
fib(2)=fib(1)+fib(0)=1+1=2

This is because of the stmts:
if x == 0 or x == 1:
return 1
And after running the code and looking at the values I see that f(12) = 233.

Answer 6

hmm. f(0) is 0 and f(1) is 1 from http://oeis.org/A000045
so
http://pastebin.com/25HtfsUT

Answer 7

good catch

Answer 8

Yeah, same at Wikipedia. Nice.

Answer 9

So for that definition the code should be:

def fib(x):
if x == 0 :
return 0
elif x == 1:
return 1
return fib(x-1) + fib(x-2)

Answer 10

I think the problem is the wrong definition of Fibonacci numbers... Robert Sedgwick (Algorithms in C) defines it as F(0)=F(1)=1. I suppose that wikipedia as well as other "unreliable sources" are wrong... So Prof. Grimson is correct. Constantly learning... Thank you guys!

Answer 11

i find mostly references for f(0) = 0 and f(1) = 1