#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import timeit


def fibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)


def fibo_non_recursive(n):
    items = [0, 1, None]
    if n in (0, 1):
        return n
    for _ in range(n):
        items[2] = items[0] + items[1]
        items[0] = items[1]
        items[1] = items[2]
    return items[2]


cache = dict()
def fibo_with_cache(n):  # NoQa E302
    global cache
    if n not in cache:
        if n in (0, 1):
            cache[n] = n
        else:
            cache[n] = fibo_with_cache(n-2) + fibo_with_cache(n-1)
    return cache[n]


if __name__ == "__main__":
    order = 30
    print("Time for simple Fibonacci function; order", order)
    n = 1
    print(n, "loop:", timeit.timeit(lambda: fibo(order), number=n))

    print("-" * 40)
    print("Time for non recursive Fibonacci function; order", order)
    n = 10000
    print(n, "loops:", timeit.timeit(lambda: fibo_non_recursive(order), number=n))  # NoQa

    print("-" * 40)
    print("Time for simple Fibonacci function with cache; order", order)
    n = 500000
    print(n, "loops:", timeit.timeit(lambda: fibo_with_cache(order), number=n))