# code

from time import time
from sys import setrecursionlimit
from functools import lru_cache

setrecursionlimit(10000000)


seen = set()

@lru_cache(None)
def solve(i):

    if i in seen:
        raise Exception("won't happen")
    seen.add(i)

    if i < 0:
        return 0

    children = [i-1, i-2]

    #best = -1
    #for j in children:
    #    best = max(best, solve(j))
    best = max(solve(j) for j in children)
    return best

lo = 8
hi = 16

t = {}

for sh in range(lo, hi):
    solve.cache_clear()
    seen = set()
    b4 = time()
    x = 1 << sh
    ret = solve(x)
    after = time()
    t[sh] = after - b4

for sh in range(lo+1, hi):
    print(t[sh] / t[sh-1])


# benchmarks

> python3.5 benchbug.py
1.689738919247116
2.3758533956162413
1.939503932244404
2.2485963817841546
2.673116937161881
2.165291507744999
2.169144123902819
> python3.6 benchbug.py
1.3893129770992367
2.2978806907378337
1.9800170794192997
2.211075649098594
2.8108688019350057
2.183536661531415
2.276095495976507
> python3.7 benchbug.py
2.3284487114704397
3.5394965277777777
3.461250766400981
3.9817901617274547
3.9458502384511354
3.8508022873532637
3.913629918463439
> python3.8 benchbug.py
1.3911355548366224
3.8274418604651164
3.201968647466278
3.902652852100649
3.5607550252355806
3.765108314488906
4.112620473996766