[abhirag]

Don'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.

[daveFNbuck]

You 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]

But 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]

I 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.