recursion logo recursion: cache

1 2 3 4 5 6
Notes

You can check that this function is much faster with the cache.

from functools import lru_cache

@lru_cache(1000)
def n_paths(start=1, end=5, jumps=(1, 2)):
    if start > end:
        return 0
    if start == end:
        return 1
    return sum([n_paths(start=start + j, end=end) for j in jumps])

The benchmarking script can be found below.

import time

for e in [10, 30, 31, 32, 33]:
    tic = time.time()
    n_paths(start=1, end=e)
    print(f"end={e} took {time.time() - tic}")