Welcome, guest | Sign In | My Account | Store | Cart

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

Python, 30 lines
 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()

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

2 comments

Matteo Dell'Amico 14 years, 5 months ago  # | flag

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

Steven Kryskalla 11 years, 8 months ago  # | flag

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.

Created by Vadim Zaliva on Mon, 2 Jul 2007 (PSF)
Python recipes (4591)
Vadim Zaliva's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks