Garbage collection of recursive inner function

Terry Reedy tjreedy at
Tue Aug 5 05:23:45 CEST 2008

from.future.import at wrote:
> I encountered garbage collection behaviour that I didn't expect when
> using a recursive function inside another function:

To understand this, it helps to realize that Python functions are not, 
in themselves, recursive.  Recursiveness at any time is a property of a 
function in an environment, which latter can change.  More specifically, 
a function call is recursive if the expression indicating the function 
to call happens to indicate the function containing the call at the time 
of evaluation just before the evaluation of the argument expressions. 
See examples below.

 >  the definition of
> the inner function seems to contain a circular reference, which means
> it is only collected by the mark-and-sweep collector, not by reference
> counting. Here is some code that demonstrates it:

The inner function is part of a circular reference that is originally 
part of the outer function, but which may survive the call to outer

> def outer():
> 	def inner(n):
> 		if n == 0:
> 			return 1
> 		else:
> 			return n * inner(n - 1)

        inner1 = inner
        def inner(n): return 1
# original inner still exists but is no longer 'recursive'

def out2():
   def inner1(n): return 1
   def inner(n):
     if n: return n*inner1(n-1)
     else: return 1
   # inner is obviously not recursive
   inner1 = inner
   # but now it is

> If the inner function is moved outside the scope of the outer
> function, gc.garbage will be empty.

With 'inner' in the global namespace, no (circular) closure is needed to 
keep it alive past the outer lifetime.

 > If the inner function is inside
> but not recursive, gc.garbage will also be empty.

Not necessarily so.  What matters is that inner has a non-local 
reference to outer's local name 'inner'.  Try
   def inner(): return inner
which contains no calls, recursive or otherwise.

 > If the outer  function is called twice,
 >  there will be twice as many objects in gc.garbage.

And so on, until gc happens.

> Is this expected behaviour?   Collecting an object when its refcount
> reaches zero is preferable to collecting it with mark-and-sweep, but

Adding 'inner = None' at the end of an outer function will break the 
cycle and with CPython, all will be collected when outer exits.
Jython and IronPython do not, I believe, do reference counting.

Adding 'del inner' gives
SyntaxError: cannot delete variable 'inner' referenced in inner scope.

> maybe there is a reason that a circular reference must exist in this
> situation. I want to check that first so I don't report a bug for
> something that is not a bug.

Not a bug, but an educational example and possibly useful to someone 
running on CPython with gc turned off and making lots of calls to 
functions with inner functions with recursive references.  I learned a 
bit answering this.

Terry Jan Reedy

More information about the Python-list mailing list