Useful when traversing a graph, which nodes assigned unique IDs and you would like to avoid loops.
Download
Copy to clipboard1 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 <lord@crocodile.org>
"""
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.
Usage example:
@norec(0, -99, [2]) 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
Looks like what you'd probably need in most cases would be a memoizing decorator (there are plenty in this cookbook).
One problem with this decorator is that it can not prevent recursion on a function which takes no arguments. I used this recipe as a basis for an improved decorator to prevent recursion. You can find it here. It works by attaching a counter to the function and incrementing the counter whenever a recursion call is made. By watching the counter you can stop the recursion before it goes too deep.