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?

mhlester · Accepted Answer · 2014-04-09 20:01:40Z

4

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

edited Apr 9, 2014 at 20:01

answered Apr 9, 2014 at 19:45

mhlester

23.3k10 gold badges55 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Eevee Over a year ago

i believe this'll end up being O(n**n) in the maximum number of stack frames actually. so, quite a while.

mhlester Over a year ago

I was just coming to that realization myself. Yikes!

Eevee Over a year ago

or maybe O(2**n), actually. astronomical either way :)

mhlester Over a year ago

@Martijn, I don't think so. You can't enter the exact same finally unless you're in a bona fide loop.

Kevin Over a year ago

This experiment indicates that the program does finish executing, but takes twice as long each time you increase the recursion limit by one. so O(2**n) is a good estimation.

|

Martijn Pieters · Accepted Answer · 2014-04-09 20:55:03Z

4

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

edited Apr 9, 2014 at 20:55

answered Apr 9, 2014 at 19:45

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

5 Comments

inspectorG4dget Over a year ago

Wish I could give another +1 for You are now falling at such a velocity you entered orbit around the interpreter

Piotr Dabkowski Over a year ago

Will it run forever or it will finally raise an exception (after VERY long time as @mhlester suggests)?

Martijn Pieters Over a year ago

@pbackup: it'll run forever. There is just one stack limit, not a square root of limits. You just keep 'recovering' then re-entering the problem by re-applying a try-finally handler.

user2357112 Over a year ago

@MartijnPieters: You don't keep rerunning the same f2 call. Try lowering the recursion limit and then testing it; you'll see that it actually does terminate.

Martijn Pieters Over a year ago

@user2357112: yes, you are right; you do fall back eventually.

Collectives™ on Stack Overflow

Python recursion RuntimeError

2 Answers 2

6 Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related