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!

### Like this:

Like Loading...

*Related*

PYTHON ROCKS

nerd

then why are you here John

Here is another way:

fibo=[0,1]

for i in range (50):

fibo.append(fibo[-1]+fibo[-2])

print fibo

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

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

Agreed! The recursive approach here doesn’t really work

how about

fibo=g.67

a=c67

fbr=(9-8a)

(n-2)

n8-7

works for me 🙂

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

Python is childs play

from functools import lru_cache

@lru_cache(maxsize=None)

def fib(n):

return n if n < 2 else fib(n-1) + fib(n-2)

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.

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.

Thanks for your comment 🙂

here is another simple way:

for num in range (15):

fibo = ((1.618033988749895**num) -(1-1.618033988749895)**num) / float (5**0.5)

print fibo

#Another simple method

for num in range (15):

fibo = ((1.618033988749895**num) -(1-1.618033988749895)**num) / float (5**0.5)

print fibo

[…] Here is a Python solution Here is a Java solution Here is a Ruby solution […]

how about this?

a=c=0

b=1

print 1

while 1:

c=a+b

a=b

b=c

print c

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.

## Example 3: Using generators

yield should be before a,b = b,a+b. Else you are missing 0 as the first output from the next calls