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
f=fibI()
f.next()
f.next()
f.next()
f.next()
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]

@Memoize
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!

Advertisements

19 thoughts on “5 Ways of Fibonacci in Python

  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.

    Thanks,
    Jeff

  2. import math
    def C(x,y):
    t=math.factorial(x-y)*math.factorial(y)
    return math.factorial(x)/t
    def fib(n):
    i=0
    t=0
    m=n-1
    while (i<n/2.0):
    t=t+C(m-i,i)
    i=i+1
    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

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s