Example of recursive and iterative Fibonacci sequence along with empirical analysis of run time

fib_fun.py

import time
current_milli_time = lambda: int(round(time.time() * 1000))

def fib_recursive(input):
    if input == 0:
        return 0
    if input == 1:
        return 1
    return fib_recursive(input - 1) + fib_recursive(input - 2)

start = current_milli_time()
for i in range(40): 
    print fib_recursive(i),

end = current_milli_time()
print "Time elapsed: %s milliseconds", str(end - start)


def fib_memoization(input):
    result_table = [None] * (input + 1)  # Create memoization table
    return fib_helper(input, result_table)

def fib_helper(input, result_table):
    if input == 0:
        return 0
    if input == 1:
        return 1
    if result_table[input] == None:
        result_table[input] = fib_helper(input - 1, result_table) + fib_helper(input - 2, result_table)
    return result_table[input]

start = current_milli_time()
for i in range(999): 
    print fib_memoization(i),

end = current_milli_time()
print "Time elapsed: %s milliseconds", str(end - start)


def fib_iterative(input):
    if input == 0:
        return 0
    if input == 1:
        return 1
    first = 0
    second = 1
    for i in range(input - 2):
        result = first + second
        first = second
        second = result
    return first + second

start = current_milli_time()
for i in range(9999): 
    print fib_iterative(i),

end = current_milli_time()
print "Time elapsed: %s milliseconds", str(end - start)