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 :-)
2007-12-15T14:07:47Z
http://www.jtauber.com/atom/full/
[ Verweis - Nachrichtenkanal ]
/blog/2007/12/15/avoiding_recursion/
[ Verweis - Eintrag ]