It's not necessary to write a specialized memorizing decorator when you could just use a generic pre-written one...such as the following straight from the PythonDecoratorLibrary:
import collections
import functools
class memoized(object):
'''Decorator. Caches a function's return value each time it is called.
If called later with the same arguments, the cached value is returned
(not reevaluated).
'''
def __init__(self, func):
self.func = func
self.cache = {}
def __call__(self, *args):
if not isinstance(args, collections.Hashable):
# uncacheable. a list, for instance.
# better to not cache than blow up.
return self.func(*args)
if args in self.cache:
return self.cache[args]
else:
value = self.func(*args)
self.cache[args] = value
return value
def __repr__(self):
'''Return the function's docstring.'''
return self.func.__doc__
def __get__(self, obj, objtype):
'''Support instance methods.'''
return functools.partial(self.__call__, obj)
You could then apply it to yourchange()
function (or any other, since it's generic) like this:
@memoized
def change(a, kinds=(50, 20, 10, 5, 1)):
if a == 0:
return 1
if a < 0 or len(kinds) == 0:
return 0
return change(a - kinds[0], kinds) + change(a, kinds[1:])
print(change(10)) # 4