def фиб(n):
    """Враћа n-ти Фибоначијев број.

    >>> фиб(20)
    6765
    """
    if n == 0 or n == 1:
        return n
    else:
        return фиб(n-2) + фиб(n-1)

# Време

def преброј(f):
    """Враћа пребројиву верзију функције f која садржи атрибут број_позива.

    >>> def фиб(n):
    ...     if n == 0 or n == 1:
    ...         return n
    ...     else:
    ...         return фиб(n-2) + фиб(n-1)
    >>> фиб = преброј(фиб)
    >>> фиб(20)
    6765
    >>> фиб.број_позива
    21891
    """
    def пребројано(*args):
        пребројано.број_позива += 1
        return f(*args)
    пребројано.број_позива = 0
    return пребројано

# Мемоизација

def мемо(f):
    """Мемоизована функција f.

    >>> def фиб(n):
    ...     if n == 0 or n == 1:
    ...         return n
    ...     else:
    ...         return фиб(n-2) + фиб(n-1)
    >>> фиб = преброј(фиб)
    >>> фиб(20)
    6765
    >>> фиб.број_позива
    21891
    >>> избројан_фиб = преброј(фиб)
    >>> фиб = мемо(избројан_фиб)
    >>> фиб(20)
    6765
    >>> избројан_фиб.број_позива
    21
    >>> фиб(35)
    9227465
    >>> избројан_фиб.број_позива
    36
    """
    кеш = {}
    def мемоизовано(n):
        if n not in кеш:
            кеш[n] = f(n)
        return кеш[n]
    return мемоизовано

# Простор

def преброј_оквире(f):
    """Враћа пребројиву верзију функције f која садржи атрибут max_број.

    >>> def фиб(n):
    ...     if n == 0 or n == 1:
    ...         return n
    ...     else:
    ...         return фиб(n-2) + фиб(n-1)
    >>> фиб = преброј_оквире(фиб)
    >>> фиб(20)
    6765
    >>> фиб.број_отворених
    0
    >>> фиб.максималан_број
    20
    >>> фиб(25)
    75025
    >>> фиб.максималан_број
    25
    """
    def пребројано(n):
        пребројано.број_отворених += 1
        пребројано.максималан_број = max(пребројано.максималан_број, пребројано.број_отворених)
        резултат = f(n)
        пребројано.број_отворених -= 1
        return резултат
    пребројано.број_отворених = 0
    пребројано.максималан_број = 0
    return пребројано

# Ред раста

def exp(b, n):
    """Враћа b на n.

    >>> exp(2, 10)
    1024
    """
    if n == 0:
        return 1
    else:
        return b * exp(b, n-1)

def квадрат(x):
    return x*x

def exp_брз(b, n):
    """Враћа b на n.

    >>> exp_брз(2, 10)
    1024
    """
    if n == 0:
        return 1
    elif n % 2 == 0:
        return квадрат(exp_брз(b, n//2))
    else:
        return b * exp_брз(b, n-1)

# Преклапање

def преклапање(m, n):
    """Враћа број чланова који се појављују и у m и у n.

    >>> преклапање([3, 5, 7, 6], [4, 5, 6, 5])
    3
    """
    број = 0
    for члан in m:
        for други in n:
            if члан == други:
                број += 1
    return број
