5 Ways of Fibonacci in Python

After learning so much about development in Python, I thought this article would be interesting for readers and to myself…

This is about 5 different ways of calculating Fibonacci numbers in Python

## Example 1: Using looping technique
def fib(n):
 a,b = 1,1
 for i in range(n-1):
  a,b = b,a+b
 return a
print fib(5)

## Example 2: Using recursion
def fibR(n):
 if n==1 or n==2:
  return 1
 return fibR(n-1)+fibR(n-2)
print fibR(5)

## Example 3: Using generators
a,b = 0,1
def fibI():
 global a,b
 while True:
  a,b = b, a+b
  yield a
print f.next()

## Example 4: Using memoization
def memoize(fn, arg):
 memo = {}
 if arg not in memo:
  memo[arg] = fn(arg)
  return memo[arg]

## fib() as written in example 1.
fibm = memoize(fib,5)
print fibm

## Example 5: Using memoization as decorator
class Memoize:
 def __init__(self, fn):
  self.fn = fn
  self.memo = {}
 def __call__(self, arg):
  if arg not in self.memo:
   self.memo[arg] = self.fn(arg)
   return self.memo[arg]

def fib(n):
 a,b = 1,1
 for i in range(n-1):
  a,b = b,a+b
 return a
print fib(5)

You may ask, all this is okay, but what’s the best way? Wait for another post on performance of these… Its on the way!


22 thoughts on “5 Ways of Fibonacci in Python

    • i like this method, this is more or less the way i went, because being able to display the whole sequence or the last value only seemed useful to me, so i had it store a list. i added a few failsafes to the code, so you can’t crash your computer with too large of values, and so it doesn’t always print the whole list…but i found it to be useful like this. it is not the most efficient way to calculate just the value, I believe the recursions get to the value faster. this spends way too much resource on indexing, methinks..

  1. You have an error in the function fibR (Example 2). When you recursively call the functions in the return statement, you are calling fib(n-1)+fib(n-2) instead of fibR(n-1)+fibR(n-2). The example script only works because fib(n) has already been defined!

    Other than that, excellent job.


  2. import math
    def C(x,y):
    return math.factorial(x)/t
    def fib(n):
    while (i<n/2.0):
    return t

  3. In your first memoization example (not the one with decorators) I don’t understand why your hashmap/dict (memo) is not declared globally. Wouldn’t this just instantiate an empty dict every time you call the function? You’re not actually storing any values for reference later since you essentially wipe the data structure every time you call the function.

    • That’s true, thanks Chris for pointing it out. I just wanted to add a simple example to demonstrate the case, but your suggestion is useful, thanks.

      • Thanks for the response Chetan, simply moving the dict to the global scope would make memoization technically work for the iterative/looping solution, although that really only improves your runtime on multiple calculations of fib (aka, fib(6) only gets a performance boost if you had explicitly run fib(5) or under previously in the same run of the program.

        From my experience with interviews with companies that ask this question, they usually want you to take your recursive function and add memoization to that since it benefits the most from it (relatively that is). You’re actually populating your hash WHILE running fib(5) as opposed to just after the fact.

  4. Example 5, with the memoization decorator, does not take full advantage of the memoization feature. You should combine Example 2’s recursive method inside Example 5’s decorated function, so that calls to fibR(n-1) and fibR(n-2) reuse the previously calculated values in the Memoization instance.

  5. here is another simple way:

    for num in range (15):
    fibo = ((1.618033988749895**num) -(1-1.618033988749895)**num) / float (5**0.5)
    print fibo

  6. #Another simple method

    for num in range (15):
    fibo = ((1.618033988749895**num) -(1-1.618033988749895)**num) / float (5**0.5)
    print fibo

  7. That’s interesting to see the Fibonacci generation using five different approaches. However, mentioning their time complexity would have made more sense for us to observe the effectiveness of each method. None the less, I get to know another way which gives two formulas to find nth Fibonacci Number in O(log n) time.
    -> F(n) = [2*F(k-1) + F(k)]*F(k) where n is even and k is n/2.
    -> F(n) = F(k)*F(k) + F(k-1)*F(k-1) where n is odd and k is (n + 1)/2.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s