... recursion: cache


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

from functools import lru_cache

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}")

Feedback? See an issue? Something unclear? Feel free to mention it here.

If you want to be kept up to date, consider signing up for the newsletter.