Recursive Collections in Python

If you are settled, then lets begin...

A recursive data structure is a collection of data where when you try and show the items of the collection, you end up in an infinite loop and could go on showing items without end.

It is best shown with Python lists, (although other mutable types that can hold mutable types work too).

A simple recursive list

In [55]:

x = [0, 1, 2]
x

Out[55]:

[0, 1, 2]

X is at present a straightforward list.

A python list object is a container of, (internal references to), other objects. lists are mutable, which means that the same list object may have its contents altered but still remain the same list object, just with updated contents. (Analogous to a chest of drawers being able to have socks in the top drawer one week but be rearranged to have ties in the top drawer later on, but still be refered to as the same chest of drawers).

What if the list x object contained itself? Contained just means that one of the referenced objects of x is x itself.

We can do that:

In [56]:

x[2] = x

Lets give python a chance to give the value of x. It should be straightforward to display the x[0], and x[1] items but what happens when it reaches x[2]? We have said that it is x and we can display x[0], and x[1], but what happens whith this x[2]...

In [57]:

x

Out[57]:

[0, 1, [...]]

Yay!
Python is smart enough to find the point of recursion and give an indication of the point of recursion by the symbol [...].

Hmm, I wonder what pprint has to offer when displaying x?

In [58]:

from pprint import pprint as pp

pp(x)

[0, 1, (Recursion on list with id=86231560)]

pprint goes further and tries to show what is being recursed into by telling you the object id.

The id of an object is a unique integer representing every object of Python. If two Python names refer to values with the same id, then they are in fact referring to the same object:

In [59]:

s = t = object()
s == t, s is t, id(s) == id(t)

Out[59]:

(True, True, True)

So if x refers to x then the id of x should equal the id of x[2]

In [60]:

id(x), id(x[2]), id(x) == id(x[2])

Out[60]:

(86231560L, 86231560L, True)

Mutual recursion

We can also have more complex recursions. In this case we will have x refer to y which refers to x...

In [61]:

x = [0, 1, 2]
y = [3, 4, 5]

x[2], y[2] = y, x

print('x = %r; y= %r' % (x, y))

x = [0, 1, [3, 4, [...]]]; y= [3, 4, [0, 1, [...]]]

This time the recursions are found where x is in y for x and where y is in x for y.

Showing the id's will help clarify things

In [62]:

print('id(x) == %i; id(y) == %i' % (id(x), id(y)))

id(x) == 86190216; id(y) == 86215816

In [63]:

pp(x)

[0, 1, [3, 4, (Recursion on list with id=86190216)]]

In [64]:

pp(y)

[3, 4, [0, 1, (Recursion on list with id=86215816)]]

Wacky indexing

In [65]:

x[2][2][2][2][0]

Out[65]:

0

In [66]:

x[2][2][2][2][2][2][2][2] == x

Out[66]:

True

Is this list recursive?

One way of finding if a lst is recursive would be to look for the '[...] sequence in the repr of a list, but it would be fragile; easily broken by a list with a string item containing '[...]'.

Lets write a better function to show if a list is recursive.

In [68]:

x1 = [0, 1, 2]
z1 = [0, 1, [2, x1], 3, [4, 5, x1]] # Not recursive
z1

Out[68]:

[0, 1, [2, [0, 1, 2]], 3, [4, 5, [0, 1, 2]]]

In [69]:

x2 = [0, 1, 2]
z2 = [0, 1, [2, x2], 3, [4, 5, x2]]
x2.append(z2) # Now make x2, and z2 mutually recursive
x2

Out[69]:

[0, 1, 2, [0, 1, [2, [...]], 3, [4, 5, [...]]]]

In [70]:

z2

Out[70]:

[0, 1, [2, [0, 1, 2, [...]]], 3, [4, 5, [0, 1, 2, [...]]]]

The isRecursive test function

In [71]:

def isRecursive(lst, seen=None):
    if seen is None:
        seen = {id(lst)}
    for item in lst: # for only works for iterables; otherwise raise TypeError
        iditem = id(item)
        if iditem in seen:
            return iditem
        else:
            seen.add(iditem)
            try:
                foundrecursion = isRecursive(item, seen)
            except TypeError:
                continue
            else:
                if foundrecursion:
                    return foundrecursion
            finally:
                seen.discard(iditem)
    return False

In [72]:

isRecursive(x1)

Out[72]:

False

In [73]:

isRecursive(z1)

Out[73]:

False

In [74]:

isRecursive(x2)

Out[74]:

87163336L

In [75]:

isRecursive(z2)

Out[75]:

85609608L

In [76]:

id(x2), id(z2)

Out[76]:

(87163336L, 85609608L)

End.