Fibonacci series - Find the fibonacci number of a given integer 'n'
#!/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 == 0:
return 0
if n == 1 or n == 2:
return 1
return (fibRecurse(n - 2) + fibRecurse(n - 1))
#/////////////////////////////////////////////////////////////////
# Iterative version - optimal computation. Works on accumulation
# and moving forward
#/////////////////////////////////////////////////////////////////
def fibIterative(n):
# Some boundary conditions
if n < 0:
print('Cannot find Fibonacci of -ve numbers. Returning -1')
return -1
if n == 0:
return 0
if n == 1 or n == 2:
return 1
a = 1 # (n-1)th element
b = 1 # (n-2)th element
for i in xrange(3, n+1):
c = a + b
b = a
a = c
return a
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)
No comments:
Post a Comment