import time

def timeit(func, repeats=1):
    """
    Return a wrapper that times the execution of a function
    """
    def timed(*args, **kargs):
        """
        Print the execution time of the function
        """
        i = 0
        time0 = time.time()
        while i < repeats:
            result = func(*args, **kargs)
            i += 1
        time1 = time.time()
        print('Execution time:', time1 - time0)
        return result
    return timed

def factorial(n):
    """Return n!

    >>> factorial(0)
    1
    >>> factorial(3)
    6
    >>> factorial(4)
    24
    """
    if n == 0:
        return 1
    return n * factorial(n - 1)

timed_factorial = timeit(factorial, 1000)

def fib_rec(n):
    """Return the nth Fibonacci number

    >>> fib_rec(0)
    0
    >>> fib_rec(1)
    1
    >>> fib_rec(5)
    5
    """
    if n == 0 or n == 1:
        return n
    return fib_rec(n - 1) + fib_rec(n - 2)

timed_fib_rec = timeit(fib_rec)

def fib_iter(n):
    """Return the nth Fibonacci number

    >>> fib_iter(0)
    0
    >>> fib_iter(1)
    1
    >>> fib_iter(5)
    5
    """
    cur, next = 0, 1
    while n > 0:
        cur, next = next, cur + next
        n -= 1
    return cur

timed_fib_iter = timeit(fib_iter)

def square(x):
    """Return x squared

    >>> square(2)
    4
    >>> square(3)
    9
    """
    return x * x

def pow_naive(b, n):
    """Return b ** n

    >>> pow_naive(2, 2)
    4
    >>> pow_naive(4, 5)
    1024
    """
    if n == 0:
        return 1
    else:
        return b * pow_naive(b, n - 1)

timed_pow_naive = timeit(pow_naive, 1000)

def pow_fast(b, n):
    """Return b ** n

    >>> pow_fast(2, 2)
    4
    >>> pow_fast(4, 5)
    1024
    """
    if n == 0:
        return 1
    elif n % 2 == 0:
        return square(pow_fast(b, n // 2))
    else:
        return b * pow_fast(b, n - 1)

timed_pow_fast = timeit(pow_fast, 1000)