Avoiding Recursion

Occasionally I implement an algorithm recursively then hit the recursion limit in Python.

For example, I just wrote this:

def clique(self, node, done=None):
    if done is None:
        done = set()
    done.add(node)
    for other_node in self.edges_by_node[node]:
        if other_node not in done:
            self.clique(other_node, done)
    return done

which hits a limit if the graph is too big.

So I rewrote it like this:

def clique(self, start_node):
    done = set()
    to_do = [start_node]
    while to_do:
        node = to_do.pop()
        done.add(node)
        for other_node in self.edges_by_node[node]:
            if other_node not in done:
                to_do.append(other_node)
    return done

There's a simple relationship between the two, quite independent of the specific task at hand. Which got me thinking about abstracting the specific task out of the recursive versus non-recursive pattern.

I guess I was having an SICP moment :-)