New answers tagged

10

One more option is to not recurse at all, but to instead compute the sequence until we get the desired term. This not only avoids the original algorithm's exponential complexity; it also avoids the at least linear (in terms of counting values) memory complexity of memoization. (Recursion/memoization can also run into implementation-specific issues such as ...


8

If you cannot use functools.cache or functools.lru_cache and if you don't understand or want to use a decorator, as shown in another answer, here a low-tech approach to memoization. Please note that the functools approach is easier, more robust, etc. But if you are not worried about all of that and just want simple code that is radically faster than your ...


6

You should use an if "__name__" == __main__: guard. From Python 3.2 you can use functools.lru_cache and from Python 3.9 you can use functools.cache to memoize the function calls, to only call T \$O(n)\$ times. Which is a fancy name for caching the input and output of the function. The way this works is by wrapping a function. Each time the ...


Top 50 recent answers are included