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

Last updated

Was this helpful?