On Fri, Feb 23, 2018 at 5:38 PM, Terry Reedy <tjre...@udel.edu> wrote:
> As to the vague 'class of problems implemented in a similar manner': Any
> function f of count N that depends of values of f for counts < N can be
> memoized the same way in Python as fibonacci. Everything said about P vs J
> for fib applies to such similar problems. The same is almost true for
> functions that depend on a pair of counts, such as the number of
> combinations of N things taken K at a time. The time benefit per space used
> is just a bit less.
The naive recursive Fibonacci function can be memoized with maxsize=2
and it gets virtually all the benefit - in fact, it becomes
effectively iterative. (I think even maxsize=1 will do that.) With
most memoization, that kind of benefit is less blatant.