Comparison of recursive and iterative implementations of Fibonacci number

fibonacci

"""
Example of how bad performance of recursive implementations can be when compared to iterative approaches.

For more in this topic, read Guido van Rossum (creator of Python programming language) blog post:
http://neopythonic.blogspot.com.br/2009/04/tail-recursion-elimination.html
"""

__author__ = "Tatiana Al-Chueyr <[email protected]>"


import time


def fibonacci_recursive(number):
    """
    Recursive implementation of Fibonacci.
    """
    if number == 0:
        return 0
    elif number == 1:
        return 1
    else:
        return fibonacci_recursive(number-1) + fibonacci_recursive(number-2)


def fibonacci_iterative(number):
    """
    Iterative implementation of Fibonacci.
    """
    before_previous, previous = 0, 1
    for item in xrange(number):
        before_previous, previous = previous, before_previous + previous
    return before_previous


def compare_fibonacci(number):
    """
    Compare Fibonacci number implementation using recursive and iterative
    approaches.
    """
    t1 = time.time()
    answer1 = fibonacci_recursive(number)
    t2 = time.time()
    time_recursive = t2 - t1

    t1 = time.time()
    answer2 = fibonacci_iterative(number)
    t2 = time.time()
    time_iterative = t2 - t1

    assert answer1 == answer2
    print("Iterative is {0}x faster".format(time_recursive/time_iterative))


if __name__ == "__main__":
    for number in xrange(32):
        compare_fibonacci(number)