Useful when traversing a graph, which nodes assigned unique IDs and you would like to avoid loops.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
def norec(an=0,defret=None,initial=): """ Recursion/loop prevention function decorator For example, could be used when traversing a graph, which nodes assigned unique IDs and you would like to avoid loops. Keyword arguments: an -- position of function argument, which is used as unique id (0-based) defret -- default return value, which is returned when recursion is detected initial -- initial content of call stack. Array of unique ids Vadim Zaliva <email@example.com> """ class decorate: def __init__(self): self.cs=initial def __call__(self, f): def new_f(*args, **kwds): id=args[an] if id in self.cs: #print "recursion detected at '%s' in %s" % (id, str(self.cs)) return defret else: self.cs.append(id) x = f(*args, **kwds) self.cs.remove(id) return x return new_f return decorate()
I have several graph traversal functions, which under certain circumstances might cause recursion loops when processing them in functional manner. I was looking for simple, monadic approach how to avoid such loops without modifying too much code.
An alternative approach would be to pass call stack down all the execution chain by adding additional argument, which is cumbersome and requires lots of code modifications.
I have chosen to return default value when recursion was detected. An alternative approach could be to throw and exception.
@norec(0, -99, ) def test(n): if n>0: return test(n-1) else: return -1
would detect recursion:
recursion detected at '2' in [2, 5, 4, 3] -99