[Python-Dev] very slow compare of recursive objects (original) (raw)

Tim Peters tim.one@comcast.net
Mon, 20 Jan 2003 10:32:50 -0500

[Tim]

Tuples can't be recursive,

[Guido]

Oh yes they can be:

>>> L = [] >>> t = (L, L) >>> L.append(L) >>>

That's an example of a tuple containing a recursive structure; there's still no way, starting at t, to get back to t. I think mutation is required for that. Like

L = [None]
t = (L, L)
L[0] = t

Then

t[0]0] is t

and that's what I mean by "recursive tuple" (a tuple that can be reached from itself).

It's not clear that this matters to the recursion-checker, though. If it indeed requires mutation to create a recursive tuple in the sense I mean it, then nesting of tuples alone can't create one. Stick a mutable container type into the mix, and the recursion-checker will eventually find that.

I expect we want to continue exempting deeply nested tuples, since they come up in real life (e.g., Python "parse trees" routinely exceed NESTING_LIMIT).