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 aLast updated
Was this helpful?