ActiveState Code

Recipe 523012: Recursion/loop prevention function decorator

Useful when traversing a graph, which nodes assigned unique IDs and you would like to avoid loops.

Python 
 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 <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()

Discussion

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

Comments

  1. 1. At 5:55 a.m. on 3 jul 2007, Matteo Dell'Amico said:

    Looks like what you'd probably need in most cases would be a memoizing decorator (there are plenty in this cookbook).

Sign in to comment