Python recursion RuntimeError

Question

def f1():
    f1()

We all know that calling this function in Python will produce RuntimeError: maximum recursion depth exceeded

I wrote its sligtly modified version:

def f2():
    try:
        f2()  #This line throws an error
    finally: #except works too
        f2()  #This line does not throw an error!

The second function runs forever without throwing RuntimeError. What's more, I was not able to stop it with CtrlC combination.

I dont understand why calling f2() does not throw RuntimeError. Can you explain it please?

Answer 1

As the stack fills up, it calls f2 inside the try until it reaches the maximum recursion depth.

Once it's reached that, it raises a RuntimeError, which is handled by the finally

That in turn raises the same RuntimeError, but now to the earlier stack, which passes along to the finally call.

Inside there, it exceeds the maximum depth again.

When a KeyboardInterrupt is raised, the program moves on to the finally all the same, and doesn't exit.

It won't technically run forever, because there's only one finally. That said, (thanks to the comments), it allows exponentially more calls, which is pretty dang close to infinity. A recursion depth of 100 would turn into 2¹⁰⁰ == 1267650600228229401496703205376.

If it took 1ms per call, it would take 465 billion years to complete. And that's just a depth of 100

Answer 2

The exception is still being thrown, but before Python can show it you are calling f2() again.

So each time the exception is raised, you sneak in another call. That recursive call is allowed (because we are one step below the limit), we cross the limit, the exception is raised again, the finally handler sneaks in another call, almost ad infinitum.

CTRL-C doesn't end the program for the same reasons; an exception is raised (KeyboardInterrupt), but again the finally: handler sends you back into recursion.

You are now falling at such a velocity you entered orbit around the interpreter.

It all does end, but the finally handlers add an exponentially growing number of extra calls before the stack can fully unwind:

>>> import sys
>>> def f2(depth=0, final=0):
...     try:
...         print depth
...         f2(depth + 1, final)
...     finally:
...         print 'finally:', final
...         f2(depth, final + 1)
... 
>>> sys.setrecursionlimit(5)
>>> f2()
0
1
2
3
finally: 0
finally: 0
2
finally: 1
finally: 0
1
2
finally: 1
finally: 1
1
finally: 2
finally: 0
0
1
2
finally: 1
finally: 1
1
finally: 2
finally: 1
0
1
finally: 2
finally: 2
0
finally: 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 7, in f2
  File "<stdin>", line 7, in f2
  File "<stdin>", line 7, in f2
  File "<stdin>", line 7, in f2
RuntimeError: maximum recursion depth exceeded