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?