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 :-)
Comments (1)
Created: Dec. 15, 2007
Last Modified: Dec. 15, 2007
Author: James Tauber
Last Modified: Dec. 15, 2007
Author: James Tauber
Scott Lamb on Dec. 15, 2007:
It looks like there are others who have thought about tail recursion optimization in Python. For example, http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088 has a decorator for it, though it appears horribly inefficient.
By the way, your backlinks from advogato are broken. I'd guess your RSS file is using jtauber.com-relative links, and advogato's syndication feature expects absolute ones. I haven't read the RSS spec in sufficient detail to know which is at fault.