why memoizing is faster

[Terry Reedy]

On 3/24/2011 8:26 PM, Fons Adriaensen wrote:
> On Thu, Mar 24, 2011 at 08:12:22PM -0400, Terry Reedy wrote:
>
>> 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.
>
> I wonder what exactly is meant by that last sentence:
>
> * It doesn't happen (since the function name is evaluated
>    to find the function to be called, as you explained).

In particular, the function name is resolved to an object when the 
function is called and executed, rather than when the function is 
compiled. To be more exact, I should have said, "A user-writen, 
Python-coded function cannot call itself" This is assuming that we 
exclude implementation-dependent hackery that subverts Python semantics 
by exploiting implementation-specific information that is not part of 
the language or its specification.

Consider

def f(): return f()

This books bad. Infinite recursion. Bad programmer...
Now continue with

f_orig=f
def f(): return 1
print(f_orig())
# 1

In context, f_orig is not recursive at all, in spite of its appearance.

Now consider this proposal: Introduce a keyword or special name, such as 
'__func__', that means 'this function', to be resolved as such just 
after compilation. With that, "def f: return __func__()" would be 
directly recursive, and any wrapper would be ignored by the __func__() call.

Wrappers are not needed to memoize with recursion either:

def fib_recur(n, _cache = [1,1]):
   if n >= len(_cache):
     _cache.append(fib_recur(n-2) + fib_recur(n-1))
   return _cache[n]

Perhaps prettier than fib_iter, posted before, but subject to external 
rebinding and stack overflow.

Both fib_recur and fib_iter calculate fib(100) as 573147844013817084101 
and fib(1000) as 
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
in a small fraction of a second.

-- 
Terry Jan Reedy