Here are two versions of how to write a fibonacci function.
The first is pretty standard:
def fibonacci(n):
if n == 0 or n == 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
This second function uses dictionary hints to store previously computed data. It’s considerably faster than the first function shown.
previous = {0: 0, 1: 1}
def fibonacci(n):
if previous.has_key(n):
return previous[n]
else:
new_value = fibonacci(n-1) + fibonacci(n-2)
previous[n] = new_value
return new_value
I didn’t write these myself, but I wanted to blog them for future reference.
February 1st, 2008 at 8:24 am
these are both pretty nice. But it is highly unusual to specifically need the Nth Fibonacci number. More commonly, you will want to loop through the numbers. Of course you could do something like this:
for i in xrange(1, x)
fib = fibonacci(i)
#more code
but it would be rather inefficient. Better is using a generator, like so:
def gen_fib(None):
a = b = 1
yield a
while 1:
yield b
a, b = b, a + b
for fib in gen_fib():
#some code using fib
the generator method is far faster than either other methods (0.085 seconds vs. 0.165 seconds on my pc). The downside is that the generator cannot be used to calculate any fibonacci number instantly. But this use of a fibonacci function is rather unusual.
February 1st, 2008 at 8:27 am
by the way, the comment system doesn’t take leading whitespace into account, which makes my code rather unreadable. consider replacing leading whitespace with non-breaking spaces, or perhaps using pre tags.