Why is this error-throwing recursive Python function jumping back and forth over the last few calls?

Question

Consider this recursive function, tapped out by a colleague of mine:

def a():
    try:
        a()
    except:
        a()

If you run it, the (Python 2.7) interpreter hangs. This surprised me because I expected that as soon as the recursion depth (say N) gets hit it would throw a RuntimeError, jump to the (N-1)th except block, get another RuntimeError, jump to the (N-2)th except, etc.

So I fleshed out the function a bit for debugging:

y = 10000

def a(x=0):
  global y
  if y:
    y -= 1
    try:
      print "T: %d" % x
      a(x+1)
    except RuntimeError:
      print "E: %d" % x
      a(x+1)

The y is simply there to force the function to terminate at some point, I don't think it otherwise changes the behaviour of the function. In my interpreter (where the recursion limit is 1000) calling a() produces sequences such as:

T: 998
E: 998
E: 997
T: 998
E: 998
E: 990
T: 991
T: 992
T: 993
T: 994
T: 995
T: 996
T: 997
T: 998
E: 998
E: 997
T: 998
E: 998
E: 996

Looking at the longer sequence, I can't discern any real pattern from it (although I confess I didn't try plotting it). I thought that maybe the stack was bouncing back and forth between N and N-M calls, where M increments every time the recursion depth was hit. But it doesn't seem to matter how big y is, the stack never unwinds more than about eight calls.

So what is really going on here inside Python? Is there a pattern to this behaviour?

Answer 1

This is an interesting problem. The reason that your expected behavior isn't reality appears to be that when the RuntimeError is raised, the offending "too recursive" stack frame is closed. This means that when the exception is caught in the next-lower stack frame, that frame can again recurse upwards until it hits the limit.

That is, you expected that as soon as the recursion depth (say N) gets hit it would:

1. throw a RuntimeError
2. jump to the (N-1)th except block
3. get another RuntimeError
4. jump to the (N-2)th except
5. etc.

Actually what happens is:

1. throw a RuntimeError
2. jump to the (N-1)th except block
3. recurse again all the way up to N
4. get another RuntimeError
5. jump to the (N-2)th except
6. recurse again all the way up to N
7. etc.

In addition, each "recurse again all the way up to N" must be unwound using the same incremental process of exception-recurse-exception. Thus, there are far more recursions than you expected.

The reason it is difficult to see in your output is that your original code does not distinguish between multiple calls with the same x value. When the 1001th call is made, the exception in the 1000th call returns control to the 999th call. This call then makes another call with x=1000, creating a parallel "lineage" of calls with certain x values.

The behavior can be seen by modifying your original code as follows:

y = 2000

def a(x=0, t=''):
    print(t + "In a({0})".format(x))
    global y
    if y:
        y -= 1
        try:
            a(x+1, t)
        except RuntimeError:
            print(t + "*** E: %d" % x)
            a(x+1, t+'\t')

This adds indentation so you can see which calls came inside which other calls. A sample of the resulting output is:

In a(986)
In a(987)
*** E: 987
*** E: 986
    In a(987)
    *** E: 987
*** E: 985
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
*** E: 984
    In a(985)
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
    *** E: 985
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
*** E: 983
    In a(984)
    In a(985)
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
    *** E: 985
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
    *** E: 984
        In a(985)
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
        *** E: 985
            In a(986)
            In a(987)
            *** E: 987
            *** E: 986
                In a(987)
                *** E: 987

(For some reason my interpreter first generates the error on the 988th call instead of the 1000th, but this doesn't change much.) You can see that every error only kicks things back up one step in the hierarchy, allowing a whole forest of "nested recursions" to occur.

This results in exponential growth of the number of calls. In fact, I tested this by setting the recursion limit to a small value (I tried 20 and 25), and confirmed that the recursion does eventually terminate. On my system, it terminates after 2**(R-12) total calls, where R is the recursion limit. (The 12 is the difference between the recursion limit and the number at which the first exception is actually raised, as seen in my example when the first exception is raised at N=988; presumably these 12 frames are somehow being "used" internally by my interpreter.)

It is unsurprising that your interpreter appeared to hang, since with a limit of 1000 this will take far longer than the age of the universe to complete.