Recursive functions (was Re: Observations on the three pillars of Python execution)

[Chris Angelico]

On Fri, Aug 5, 2011 at 9:22 AM, Thomas Jollans <t at jollybox.de> wrote:
> On 05/08/11 09:20, Eric Snow wrote:
>> Object available during code object execution:
>> (M) no
>> (C) no
>> (F) no
> (F) yes.
>
> cf. recursion.

Is it? As I understand it, a Python function is not able to reference
"itself" but must reference its own name. This means that assigning
that function to something else stops it being recursive:

#####
>>> def foo(x):
	print(x)
	if x>3: foo(x-1)

>>> foo(5)
5
4
3
>>> bar=foo
>>> bar(5)
5
4
3
>>> def foo(x):
	print("Foo",x)
	if x>3: foo(x-1)

>>> foo(5)
Foo 5
Foo 4
Foo 3
>>> bar(5)
5
Foo 4
Foo 3
#####

bar() is not a recursive function, even though foo() was and is. I've
just played around with a decorator, though; this appears to work:

>>> def recursive(f):
	l=list(f.__defaults__)
	l[-1]=f
	f.__defaults__=tuple(l)
	return f
>>> @recursive
def quux(x,quux=None):
	print("Quux",x)
	if x>3: quux(x-1)
>>> foo=quux
>>> def quux(x):
	print("Stopping.")
>>> quux(5)
Stopping.
>>> foo(5)
Quux 5
Quux 4
Quux 3

Effectively, the decorator binds the function's own self to its last
default parameter, thus holding a cyclic reference (unlikely to be an
issue - people won't be creating and destroying functions frequently,
so GC issues shouldn't arise). The last parameter doesn't have to have
the name of the function; this works with lambdas:

>>> recursive(lambda x,_=None: print("Lambda",x) or (x>3 and _(x-1) or None))(5)
Lambda 5
Lambda 4
Lambda 3

Yes, this is a pretty stupid example. But is this sort of decorator
useful? It's not like people regularly want recursive lambdas.

Chris Angelico