Why does this Python script create an infinite loop? (recursion)

Question

Why/how does this create a seemingly infinite loop? Incorrectly, I assumed this would cause some form of a stack overflow type error.

i = 0

def foo () :
    global i

    i += 1
    try :
        foo()
    except RuntimeError :
        # This call recursively goes off toward infinity, apparently.
        foo()

foo()

print i

Well, you just keep on calling foo, with no stopping condition, so it will continue to recurse forever. And even when you get an exception, you recurse again. — Some programmer dude
– Some programmer dude, Commented Jun 27, 2012 at 8:59
Shouldn't Python run out of memory or something? Or is the call stack cleared after the RuntimeError? — rectangletangle
– rectangletangle, Commented Jun 27, 2012 at 9:02
@RectangleTangle you should use just return in except statement not return foo(), see my solution below. — Ashwini Chaudhary
– Ashwini Chaudhary, Commented Jun 27, 2012 at 9:06
Wonder why there're so little subscribers to the stackoverflow tag — unkulunkulu
– unkulunkulu, Commented Jun 27, 2012 at 9:18

monkut · Accepted Answer · 2012-06-27 09:15:29Z

6

The RuntimeError exception will be raised if the recursion limit is exceeded.

Since you're catching this exception, your machine is going to continue on, but you're only adding to a single global int value, which doesn't use much memory.

You can set the recursion limit with sys.setrecursionlimit(). The current limit can be found with sys.getrecursionlimit().

>>> import sys
>>> sys.setrecursionlimit(100)
>>>
>>> def foo(i):
...     i += 1
...     foo(i)
...
>>> foo(1)
Traceback (most recent call last):
  ...
  File "<stdin>", line 3, in foo
RuntimeError: maximum recursion depth exceeded
>>>

If you want to run out of memory try consuming more of it.

>>> def foo(l):
...     l = l * 100
...     foo(l)
...
>>> foo(["hello"])
Traceback (most recent call last):
  ...
  File "<stdin>", line 2, in foo
MemoryError
>>>

edited Jun 27, 2012 at 9:15

answered Jun 27, 2012 at 9:09

monkut

44.1k26 gold badges133 silver badges161 bronze badges

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

Comments

moooeeeep · Accepted Answer · 2012-06-27 10:59:51Z

If you change the code to

i = 0
def foo ():
    global i
    i += 1
    print i
    try :
        foo()
    except RuntimeError :
        # This call recursively goes off toward infinity, apparently.
        foo()
    finally:
        i -= 1
        print i

foo()

You'll observe that the output oscillates short below 999 (1000 being Python's default recursion limit). That means, when the limit is hit (RuntimeError) that last call of foo() is terminated, and another one is set off to replace it immediately.

If you raise a KeyboardInterrupt you'll observe how the entire trace is being terminated at once.

UPDATE

Interestingly the second call of foo() is not protected by the try ... except-block anymore. Therefore the application will in fact terminate eventually. This becomes apparant if you set the recursion limit to a smaller number, e.g. the output for sys.setrecursionlimit(3):

$ python test.py
1
2
1
2
1
0
Traceback (most recent call last):
  File "test.py", line 19, in <module>
    foo()
  File "test.py", line 14, in foo
    foo()
  File "test.py", line 14, in foo
    foo()
RuntimeError

Collectives™ on Stack Overflow

Why does this Python script create an infinite loop? (recursion)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related