Recursive lists

Duncan Booth duncan.booth at invalid.invalid
Tue Jul 24 12:16:48 CEST 2007


mizrandir at gmail.com wrote:

> Can someone tell me why python doesn't crash when I do the following:
> 
>>>> a=[]
>>>> a.append(a)
>>>> print a
> [[...]]
>>>> print a[0][0][0][0][0][0][0]
> [[...]]
> 
> How does python handle this internally? Will it crash or use up lot's
> of memory in similar but more complicated cases?
> 
> 

No, it remembers internally which objects it has seen when converting 
them with str or repr. The C api includes functions Py_ReprEnter() and 
Py_ReprLeave() which the builtin objects call when they enter/leave 
repr. If Py_ReprEnter() returns 0 the object will return its 
representation, on subsequent calls Py_ReprEnter() returns 1 and the 
object knows it is being recursed.

If you have your own recursive data structures then you may have to take 
your own precautions against recursion. The simplest way to do this is 
to make sure that the recursion always goes through a builtin object 
such as a list or dictionary.

>>> class C:
...     def __repr__(self):
...         return "<C %r>" % self.inner
...     inner = None
...
>>> c = C()
>>> c.inner = c
>>> c
  File "<stdin>", line 3, in __repr__
  File "<stdin>", line 3, in __repr__
  File "<stdin>", line 3, in __repr__
  ... and so on ...
  File "<stdin>", line 3, in __repr__
  File "<stdin>", line 3, in __repr__
  File "<stdin>", line 3, in __repr__
RuntimeError: maximum recursion depth exceeded
>>> c.inner = [c]
>>> c
<C [<C [...]>]>

N.B. Don't use a tuple here as tuples don't check for recursion. That's 
because tuples cannot be recursive except by containing another 
recursive data structure such as a list, dict, or user-defined object.



More information about the Python-list mailing list