Sunday, October 16, 2016

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