Rebrained!

Fibonacci – Python

Ok so if you’re interviewing for a programming job you have to be able to whip out a quick Fibonacci sequence at the drop of a hat, even if inelegant. This prints the fib series for n terms:

>>> def fib(n):
	a,b=0,1
	for i in range(n):
		print a,
		a,b=b,b+a

>>> fib(10)
0 1 1 2 3 5 8 13 21 34
>>>
>>>

Here’s a recursive approach:

>>> def fib(n,a=0,b=1,counter=0):
	print a,
	if counter<(n-1): fib(n,b,a+b,counter+1)

>>> fib(10)
0 1 1 2 3 5 8 13 21 34
>>>

Python has a nice concept called iterators which can be used as well. Basically you implement an __iter__ method, and then code a next method, and then you can use your class in a for loop.

>>> class fib():
	def __init__(self):
		self.a,self.b=0,1
	def __iter__(self):
		return self
	def next(self):
		ret=self.a
		self.a,self.b=self.b,self.a+self.b
		return ret

>>> for i in fib():
	print i,
	if i>10: break

0 1 1 2 3 5 8 13
>>>

You can get the benefit of an iterator in Python without the __iter__ and next methods – you just have to invoke yield somewhere in your function and you have a Generator – which will generate an iterator.

>>> def fib(a=0,b=1):
	while True:
		yield a
		a,b=b,a+b

>>> fib=fib()
>>> for i in range(10): print fib.next(),

0 1 1 2 3 5 8 13 21 34
>>>

Also using recursion, generating the nth fib term (though starting at 1). Somewhat of a brainstretcher to think through what’s going on in this recursion though. And I think something like O(2^n) time.

>>> def fib(n):
	    if n<=1: return n
	    return fib(n-1)+fib(n-2)

>>> fib(10)
55

Another using the python slice functionality:

def fib(num):
    fib=[0,1]
    while len(fib)
Anybody have another favorite fib implementation?