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

consider recursive function, tapped out colleague of mine:

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

if run it, (python 2.7) interpreter hangs. surprised me because expected recursion depth (say n) gets hit throw runtimeerror, jump (n-1)th except block, runtimeerror, jump (n-2)th except, etc.

so fleshed out function bit 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 there force function terminate @ point, don't think otherwise changes behaviour of function. in interpreter (where recursion limit 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 @ longer sequence, can't discern real pattern (although confess didn't try plotting it). thought maybe stack bouncing , forth between n , n-m calls, m increments every time recursion depth hit. doesn't seem matter how big y is, stack never unwinds more 8 calls.

so going on here inside python? there pattern behaviour?

this interesting problem. reason expected behavior isn't reality appears when runtimeerror raised, offending "too recursive" stack frame closed. means when exception caught in next-lower stack frame, frame can again recurse upwards until hits limit.

that is, expected recursion depth (say n) gets hit would:

1. throw runtimeerror
2. jump (n-1)th except block
3. get runtimeerror
4. jump (n-2)th except
5. etc.

actually happens is:

1. throw runtimeerror
2. jump (n-1)th except block
3. recurse again way n
4. get runtimeerror
5. jump (n-2)th except
6. recurse again way n
7. etc.

in addition, each "recurse again way n" must unwound using same incremental process of exception-recurse-exception. thus, there far more recursions expected.

the reason difficult see in output original code not distinguish between multiple calls same x value. when 1001th call made, exception in 1000th call returns control 999th call. call makes another call x=1000, creating parallel "lineage" of calls x values.

the behavior can seen modifying original code 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 can see calls came inside other calls. sample of 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 reason interpreter first generates error on 988th call instead of 1000th, doesn't change much.) can see every error kicks things 1 step in hierarchy, allowing whole forest of "nested recursions" occur.

this results in exponential growth of number of calls. in fact, tested setting recursion limit small value (i tried 20 , 25), , confirmed recursion terminate. on system, terminates after 2**(r-12) total calls, r recursion limit. (the 12 difference between recursion limit , number @ first exception raised, seen in example when first exception raised @ n=988; presumably these 12 frames somehow being "used" internally interpreter.)

it unsurprising interpreter appeared hang, since limit of 1000 take far longer age of universe complete.