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]:
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]:
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)

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]:
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]:

In [55]:

```
x = [0, 1, 2]
x
```

Out[55]:

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]:

Yay!

Python is smart enough to find the point of recursion and give an indication of the point of recursion by the symbol

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)
```

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]:

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]:

## 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))

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)))

In [63]:
pp(x)

In [64]:
pp(y)

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))
```

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)))
```

In [63]:

```
pp(x)
```

In [64]:

```
pp(y)
```

## Wacky indexing

##
In [65]:
x[2][2][2][2][0]

Out[65]:
In [66]:
x[2][2][2][2][2][2][2][2] == x

Out[66]:

In [65]:

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

Out[65]:

In [66]:

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

Out[66]:

## 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]:
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]:
In [70]:
```
z2
```

Out[70]:

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]:

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]:

In [70]:

```
z2
```

Out[70]:

### 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]:
In [73]:
isRecursive(z1)

Out[73]:
In [74]:
isRecursive(x2)

Out[74]:
In [75]:
isRecursive(z2)

Out[75]:
In [76]:
id(x2), id(z2)

Out[76]:

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]:

In [73]:

```
isRecursive(z1)
```

Out[73]:

In [74]:

```
isRecursive(x2)
```

Out[74]:

In [75]:

```
isRecursive(z2)
```

Out[75]:

In [76]:

```
id(x2), id(z2)
```

Out[76]:

## No comments:

## Post a Comment