4 ms·
Someone recently pointed out to me you can bypass the recursion limit with an inbuilt decorator, because it's basically a memoiser. lru_cache, from the functoo
by shakna 9y ago
Someone recently pointed out to me you can bypass the recursion limit with an inbuilt decorator, because it's basically a memoiser.
lru_cache, from the functools library.
The example given in the docs [0] is:
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
[0] https://docs.python.org/3/library/functools.html#functools.lru_cache https://docs.python.org/3/library/functools.html#functools.l...
- kqr 9y agoThis only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.
- abhirag 9y agoDon't dismiss one of my favorite higher order functions so soon :) "Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time." -- Steven Skiena lru_cache decorator is great for people who are happy to let the language handle the caching of results for them, and often leads to code which is much more concise than the dynamic programming approach. The limitation you are referring to is that the decorator uses a dictionary to cache results and that dictionary uses the arguments as keys so the arguments need to be hashable. That limitation can be avoided by using immutable data structures (Clojure also has a higher order function called memoize which does the same thing and has no limitations because the core data structures in Clojure are immutable) and although Python not having structural sharing can mean that this approach can hurt memory and GC efficiency a bit, but that trade-off is at least worth considering :) Still have to keep the stack depth less than sys.getrecursionlimit() so no substitute for tail recursion but surely a substitute for dynamic programming in a lot of cases.
- deleted 9y ago[deleted]
- daveFNbuck 9y agoYou can only avoid the recursion limit in cases where dynamic programming would also work, as you have to explicitly call the function in reverse stack order to avoid having the stack build up. If you want fib(10000) you need to call fib(1) through fib(9999) first, as if you were implementing a dynamic programming solution. This isn't dismissive. lru_cache is one of my favorites too, but it has limitations.
- abhirag 9y agoBut that isn't a limitation of lru_cache, for example the same higher order function when used in Clojure i.e. memoize with recur for tail recursion will not cause stack overflow. The stack build up is because python doesn't support tail call optimization, not a limitation of lru_cache, just wanted to make it clear because you can use similar higher order functions in other languages which support tail call optimization without any limitations. Deep recursion in Python without sys.setrecursionlimit() is probably not a good idea, memoization can't help you in that. My point was geared towards presenting this pattern of memoization using a higher order function + recursion as an alternative to dynamic programming and in languages with tco and immutable data structures it works beautifully :)
- daveFNbuck 9y agoI agree that this isn't a limitation of the Platonic ideal of an lru_cache function. I thought we were talking about actual Python code.
- e12e 9y agoIt's worth pointing out that python expands the datatype of numbers as needed (ending up at BigInt or similar, I belive). So any stack rewriting would have to accommodate an accumulator that starts as an integer and expands to arbitrarily many bits. It might be easily handled as I guess all arguments are references to python objects, and the regular code for expanding numbers could switch out the reference - but the point remains that proper tail call optimization in python needs to deal with objects as arguments.
- kqr 9y agoThis does not seem to me like a big hurdle. Surely this is the sort of thing that should be hidden in the Integer class?
- d0mine 9y agoIt won't help unless you call it in a specific order e.g., fib(10_000) may produce RecursionError unless you run for n in range(10_000): fib(n)
- shakna 9y agoRight, it's a memoiser. You side-step some recursion through previously stored results. It works well for some class of algorithms, which coincides with quite a large subsection of problems where TCO would help formulate algorithms. There are still a bunch of limits, because you're caching results, not eliminating call frames. The first obvious drawback is performance and memory use: All results get stored in a dictionary.
- deleted 9y ago[deleted]
- naveen99 9y agoIs that really tail recursion though ? Seems like you are making two recursive calls to fib(). I thought tail recursion requires a single final call to recursive function. Your memorization helps, but seems you will still run out of stack space if you call it with a big number without a warm up.
- kahnjw 9y agoI don’t think op is claiming that method is tail recursive, just pointing out you can get away with using recursion and LRU cache.