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