Fibonacci Number
#!/usr/bin/python
import sys
#/////////////////////////////////////////////////////////////////
# Recursive version - revisits the same computation multiple times
#/////////////////////////////////////////////////////////////////
def fibRecurse(n):
# Some boundary conditions
if n < 0:
print('Cannot find Fibonacci of -ve numbers. Returning -1')
return -1
if n < 2:
return n
return (fibRecurse(n - 2) + fibRecurse(n - 1))
#/////////////////////////////////////////////////////////////////
# Iterative version - optimal computation. Works on accumulation
# and moving forward
#/////////////////////////////////////////////////////////////////
def fibIterative(n):
#
if n < 0:
print('fib of -ve number cannot be found')
return -1
if n < 2:
return n
a = 1 # (n-1)th element
b = 0 # (n-2)th element
for i in xrange(2, n+1):
c = a + b
b = a
a = c
return a
#////////////////////////////////////////////
# using dynamic programming with memoization
#////////////////////////////////////////////
fibCache = {}
def fibDP(n):
if n in fibCache:
return fibCache[n]
else:
if n < 2:
fibCache[n] = n
else:
fibCache[n] = fibDP(n-2) + fibDP(n-1)
return fibCache[n]
if __name__ == "__main__":
if len(sys.argv) == 2:
n = int(sys.argv[1])
else:
print 'Usage - requires 1 arguement (n): progName n'
exit(0)
result = fibRecurse(n)
print("fibonacci - recursive of: ", n, " is: ", result)
result = fibIterative(n)
print("fibonacci - iterative of: ", n, " is: ", result)
result = fibDP(n)
print("fibonacci - DP of: ", n, " is: ", result)
Last updated
Was this helpful?