Question

sanity check--what am I doing wrong copying the fibonacci function?

Answer 1

I think this is exactly what Professor Guttag uses in Lecture 13:

def fib(n):
global numCalls
numCalls += 1
print 'fib called with ', n
if n <= 1:
return 1
else:
return fib(n-1) + fib(n-2)
numCalls = 0
n = 6
res = fib(n)
print 'fib of ', n,' = ',res, 'numCalls = ',res

but when I run it, it gives me fib(6) = 13

What am I missing?

Answer 2

Nevermind. 13 is the answer he got in the lecture as well. I was just printing res instead of numCalls and that got me confused.

Although, according to http://en.wikipedia.org/wiki/Fibonacci_number, fib(6) actually IS 8, which is what he 'corrects' early in the lecture.

Answer 3

Fib(n) is the sum of the previous two numbers in the series. It's traditional to start with 0,1 which makes fib(6)=8 (the series is 0,1,1,2,3,5,8). But, you can also start with 1,1 (which is easier to code; if n<=1 return 1), which makes fib(6)=13 (the series is 1,1,2,3,5,8,13).

Answer 4

Thanks!