import time
def FibRek(n):
    '''Fibonacci s klasično rekurzijo '''
    if n == 0: return 1
    if n == 1: return 1
    return FibRek(n-2) + FibRek(n-1)

def FibMem(n):
    ''' s pomočjo globalnega slovarja glCache'''
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n in glCache:
        return glCache[n]
    # ni ga v slovarju
    rez = FibMem(n-2) + FibMem(n-1)
    glCache[n] = rez # si ga zapomnimo
    return rez

def FibMem_2(n):
    '''ne pacamo okoli s slovarji'''
    def FibMemLok(n): # lokalna funkcija
        ''' s pomočjo slovarja glCache iz "nosilne funkcije"'''
        if n == 0 or n == 1:
            return 1
        if n in glCache:
            return glCache[n]
        # ni ga v slovarju
        rez = FibMemLok(n-2) + FibMemLok(n-1)
        glCache[n] = rez # si ga zapomnimo
        return rez
    # gl. fun
    glCache = dict() # nastavimo slovar
    return FibMemLok(n) # izvedemo lokalno funkcijo

n = int(input('Fibonacci: '))
# merimo čas
zacRek = time.process_time()
rezRek = FibRek(n)
konRek = time.process_time()
print('Rekurzija:' + 8*'\t', rezRek, '\t', konRek - zacRek)

zacMem = time.process_time()
koliko = 10000
glCache = dict()  # tukaj!
for i in range(koliko):
    rezMem = FibMem(n)
konMem = time.process_time()
print('memoizacija - izvedemo ' + str(koliko) + ' ponovitev, a "goljufamo":\t\t\t\t\t   ', rezMem, 2*'\t', (konMem - zacMem)/koliko)

zacMem = time.process_time()
koliko = 10000
for i in range(koliko):
    glCache = dict()  # tukaj!
    rezMem = FibMem(n)
konMem = time.process_time()
print('memoizacija - izvedemo ' + str(koliko) + ' ponovitev in "pošteno":\t\t\t\t\t     ', rezMem, 2*'\t', (konMem - zacMem)/koliko)

zacMem = time.process_time()
koliko = 10000
for i in range(koliko):
    rezMem = FibMem_2(n)
konMem = time.process_time()
print('memoizacija - izvedemo ' + str(koliko) + ' ponovitev in "brez packanja":\t   ', rezMem, 2*'\t', (konMem - zacMem)/koliko)