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 fib(n-1)+fib(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!

Overloading in Python

Some say Python doesn’t allow overloading of methods or constructors. Well, they are right in some way!  A coding example below,

def add(a,b):
    return a+b

def add(a,b,c):
    return a+b+c

print add(4,5)

If you try to run the above piece of code, you get an error stating, “TypeError: add() takes exactly 3 arguments (2 given)”. This is because, Python understands the latest definition of method add() which takes only two arguments. Even though a method add() that takes care of three arguments exists, it didn’t get called. Hence you would be safe to say, overloading methods in Python is not supported.

But, then there are folks who are more than willing to say, ‘Oh! Python supports all!’ Yes, Python supports overloading but in a Pythonic way. Here’s an example,

def add(instanceOf, *args):
    if instanceOf == 'int':
        result = 0
    if instanceOf == 'str':
        result = ''
    for i in args:
        result = result + i
    return result

print add('int', 3,4,5)
print add('str', 'I',' am',' in', ' Python')

Output:
12
I am in Python

In the above code snippet, two things are achieved:

-          Irrespective of the different number of arguments, method add() works well

-          Also, based on the data type of input, data  type of output is changed

So, overloading IS there in Python!!

Mystery with remove and pop in Python lists

Thanks Vishal for his inputs on this..

According to python docs

list.remove(x)

Remove the first item from the list whose value is x. It is an error if there is no such item.

list.pop([i])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

Lets try out some code around these two functions

Scenario 1

list = range(10)
for iter in list:
    list.pop()
    print list

Output of the above code snippet is:
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4]

Change in expectation? While one would expect all the elements would be removed from the list, only the later half got removed.
This is because,

iteration	iter	elements poped
1	0	9
2	1	8
3	2	7
4	3	6
5	4	5
6	5	No element in list?

So when iter become 5 there is no element at that index location

Scenario 2

list = range(10)
for element in list:
    list.remove(element)
    print list

Output of the above code snippet is:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 5, 6, 7, 8, 9]
[1, 3, 5, 7, 8, 9]
[1, 3, 5, 7, 9]

Again, I would expect all elements to be removed. But now I’m smart to understand,

iteration	iter	element removed
1	0	0
2	1	list[1] = 2
3	2	list[2] = 4
4	3	list[3] = 6
5	4	list[4] = 8
6	5	No element?