Detecting recursion loops

Carl Banks pavlovevidence at gmail.com
Wed Nov 29 16:48:13 CET 2006


robert wrote:
> My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
> What would be a good method to detect recursion loops and stop it by user-Exception (after N passes or some complex criteria) without passing a recursion counter parameter through all the funcs?


1. You could catch RuntimeError at the top, check whether it's
recursion depth exception, and raise a user exception if it is.

2. Consider whether you're unwittingly trying to cover up a bug.  ISTM
no matter how problematic the input is, you should at least be able to
make progress on it.  Are you getting this error because, say, you're
not incrementing a counter somewhere, and thus recalling a function
with the same arguments again?

3. Also consider whether you could rewrite the code to be
non-recursive.  Usually when I process input recursively, the input is
allowed to be arbitrarily deeply nested.  (In that case I think it
would be a mistake to arbitrarily limit depth.)   But it sounds to me
like your input might be inherently non-nestable.  If that's the case,
it might be possible to get rid of the recursion altogether, or at
least to put in error checking that detects when input is at an invalid
depth.

4. If those concerns don't apply, and you do need to detect recursion,
I'd suggest using a global dictionary to track function calls.  If you
have a function parse_something that you want to track, you could
define a dict like this:

_call_count = { parse_something: 0 }

And change parse_something to adjust its own counter:

def parse_something():
    _call_count[parse_something] += 1
    check_invalid_recursion()
    ....
    _call_count[parse_something] -= 1

(You could define a decorator to do this more easily; that's left as an
excercise.)

The check_invalid_recursion() function would inspect _call_count and
raise an exception based on any criteria you want.

5. In CPython, you could just inpect the stack frame and look for
duplicated function calls.  See the documentation for sys._getframe.


Carl Banks




More information about the Python-list mailing list