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!

27 thoughts on “5 Ways of Fibonacci in Python

    1. aqqmin

      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..

      Like

  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

    Like

  2. Victor

    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

    Like

  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.

    Like

    1. Chetan Giridhar

      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.

      Like

      1. 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.

        Like

  4. Walter Huf

    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.

    Like

  5. Pingback: testing ninja | Job Interview Questions: Fibonacci numbers

  6. 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.

    Like

  7. G.J.Kim

    Your #4 memoization function begins for every function call the entire recursive looping anew.

    There is a much more efficient way. That the function stores during the entire session all calculated results.
    And if you do sth else and later call the function – the function still has in memory all the previous results.

    It is done by this:

    # this memoize function returns a new helper function
    # which is a closure – so has the memo-dicitonary as a hidden (encapsulated) state.
    def memoize(f):
    memo = {}
    def helper(x):
    if x not in memo:
    memo[x] = f(x)
    return memo[x]
    return helper

    # this is your example # 1
    def fib(n):
    if n == 0:
    return 0
    elif n == 1:
    return 1
    else:
    return fib(n-1) + fib(n-2)

    fib = memoize(fib)

    # here the magic happens!
    # fib is a new helper function which took the fold fib and wraps the memo dicitonary around it
    # as a hidden/encapsulated inner state – and if you add new values to it – the values
    # stay until the nexa call of the new fib().

    # fib(10) # it calculates the first 10 fibonacci numbers – but keeps in memory them all –
    # and if you next time call fib(15) – all the values until fib(10) are “remembered”
    # and only fib(11) to fib(14) calculated in addition by the recursive (now inner) fib() function!

    # so this is a far more efficient way than your #4
    # because with your memoize(fib, 10) – all the fib(1) to fib(10) are calculated on the way.
    # and if you next time call memoize(fib, 15), then it has to calculate fib(1) to fib(15) anew.
    # Just that during this new round just repetitive calculations of same fib(n) are avoided.

    That is the difference if you create a closure – you get an encapsulated hidden inner state
    which the new fib() carries with it – and during the entire program,
    the function has a memory of previously calculated values.

    Like

    1. G.J.Kim

      And instead of the

      def fib(n):
      if n == 0:
      return 0
      elif n == 1:
      return 1
      else:
      return fib(n-1) + fib(n-2)

      fib = memoize(fib)

      one can write:

      @memoize
      def fib(n):
      if n == 0:
      return 0
      elif n == 1:
      return 1
      else:
      return fib(n-1) + fib(n-2)

      # this would be #5a – without a callable class just using functions!
      # and I guess #5a will be faster than your #5, since it has some class/function calls less.

      Like

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