On 3/24/2011 9:48 AM, Andrea Crotti wrote:
I was showing a nice memoize decorator to a friend using the classic fibonacci problem.--8<---------------cut here---------------start------------->8--- def memoize(f, cache={}): def g(*args, **kwargs): # first must create a key to store the arguments called # it's formed by the function pointer, *args and **kwargs key = ( f, tuple(args), frozenset(kwargs.items()) ) # if the result is not there compute it, store and return it if key not in cache: cache[key] = f(*args, **kwargs) return cache[key] return g # without the caching already for 100 it would be unfeasible @memoize def fib(n): if n<= 1: return 1 else: return fib(n-1) + fib(n-2)
The irony of this is that memoizing 'recursive' functions with a decorator depends on the fact the Python does not have truly recursive functions. A function cannot call itself directly. It can only call whatever callable is bound externally to its definition name. Hence, memoize rebinds the definition name (in this case 'fib') to a wrapper, so that the function once known as 'fib' no longer calls itself but calls the wrapper instead.
If Python did what some have asked, which is to make 'recursive' functions actually recursive by replacing a local variable that matches the function name (in this 'fib') with a direct reference to the function itself, as a constant (and this could be done), then the wrapper would not get called from within the function.
-- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
