why memoizing is faster

[Terry Reedy]

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