Recursive Play

A few days ago, I needed to collapse any depth of nested lists to a single list.  Using the ability of a Python function to call itself (recursion), one is able to write a short and fairly straightforward routine for flattening a list containing any number of nested lists.

Here is the function I wrote:

def recursive_list_collapse(x):
    if type(x) == type(‘a’) or type(x) == type(1) or type(x) == type(1.1):
        # if the object is already a charater,
        # just return it as a list of 1 char
        return [x]
    else:
        # if the object is a list, step through the objects
        # in the list and call myself with each object
        tmp = []
        for a in x:
            tmp += recursive_list_collapse(a)
    return tmp

Wikipedia has a nice article on Recursion.

It’s not quite true that the method will collapse any number of lists–the depth is limited by the number of recursive calls to the function that the environment can support.  Each time the method is called, the environment must store the information from the currently running method so that it can pick it back up again when the function call on the next to last line returns it’s sublist.  If you run out of scratch pad space to remember where you are, the methods cause an error.

The Wikipedia articles doesn’t make much of a concept that is tied to recursion.  Strictly speaking, recursion is infinite. But to do something useful, we need to stop at some point.

Pure recursion goes all the way down, but with self-reference (a model of self that allows decision making), recursion can be terminated and do something useful.  It is difficult (impossible?) to find the "bottom" of the recursive method without some type of self-reference, without a model of at least part of self. In the method above, I use the ability of Python to look at the type of data in the list to determine if (a) it is another list–therefore, to recursively call itself with the sublist; or (b) if the item is a fundamental type, don’t call the function again. Other recursive methods add a counter to the type passed in the recursive call–meta data–to keep track of self.

To explore the self-reference idea in another way, I rewrite the a non-recursive version of the method that uses a string manipulation algorithm.  This output is identical to the routine above.  This time, the method is to change representation to a string, manipulate the string to remove the "extra" list markers.  But you can’t just leave it a string, or it is not the same method. Here’s the interesting self-reference part–Python allows you to execute the string as a program statement to turn it back into a list type using exec(‘r=’+ string_manipulation(example)).

def string_manipulation(x):
    last = ”
    candidate = ”
    tmp = ”
    # walk through string with all spaces removed
    for c in str(x).replace(‘ ‘,”):
        if c == ‘[‘ or c == ‘]’:
            candidate = ‘,’
        else:
            candidate = c
        if last != ‘,’:
            tmp += candidate
            last = candidate
        elif candidate != ‘,’:
            tmp += candidate
            last = candidate
    return ‘[‘ + tmp[1:-1] + ‘]’

Neat.

P.S. This post was a strange coincidence as BFD emailed after I had started it to talk about recursion. Neat.

——–

Here’s the full program listing:

def recursive_list_collapse(x):
    if type(x) == type(‘a’) or type(x) == type(1) or type(x) == type(1.1):
        # if the object is already a charater,
        # just return it as a list of 1 char
        return [x]
    else:
        # if the object is a list, step through the objects
        # in the list and call myself with each object
        tmp = []
        for a in x:
            tmp += recursive_list_collapse(a)
    return tmp

def string_manipulation(x):
    last = ”
    candidate = ”
    tmp = ”
    # walk through string with all spaces removed
    for c in str(x).replace(‘ ‘,”):
        if c == ‘[‘ or c == ‘]’:
            candidate = ‘,’
        else:
            candidate = c
        if last != ‘,’:
            tmp += candidate
            last = candidate
        elif candidate != ‘,’:
            tmp += candidate
            last = candidate
    return ‘[‘ + tmp[1:-1] + ‘]’

example = [[‘a’,2],[3,[4,4.5]],[‘d’,[5.5,’f’]],[[[‘g’],’h’],’i’,’j’],’k’]
print ‘Nested List:\n’,example

r = recursive_list_collapse(example)
print ‘Collapsed with recursion:\n’,r

exec(‘r=’+ string_manipulation(example))
print ‘Collapsed with strings and reflection:\n’,r

And the ouput:

$ python recursion.py
Nested List:
[[‘a’, 2], [3, [4, 4.5]], [‘d’, [5.5, ‘f’]], [[[‘g’], ‘h’], ‘i’, ‘j’], ‘k’]
Collapsed with recursion:
[‘a’, 2, 3, 4, 4.5, ‘d’, 5.5, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’]
Collapsed with strings and reflection:
[‘a’, 2, 3, 4, 4.5, ‘d’, 5.5, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’]