3

So when toying with Python, I noticed that there is basically no limit on the program's stack size (kept performing power operations on a number, the precision stayed perfect even after getting to like thousands of digits). This makes me wonder: what if I accidentally got into an infinite recursive loop in Python? Would the compiler notice and throw a stack overflow error? Or would the program just crash? Would my CPU combust? This isn't something that I'd be eager to test myself, honestly.

Coffee Maker
  • 1,543
  • 1
  • 16
  • 29
  • possible duplicate of [Python max recursion , question about sys.setrecursionlimit()](http://stackoverflow.com/questions/7081448/python-max-recursion-question-about-sys-setrecursionlimit) – Cory Kramer Jul 22 '14 at 23:16
  • Python has a recursion limit that you can set by sys.setrecursionlimit: https://docs.python.org/2/library/sys.html#sys.setrecursionlimit – mgilson Jul 22 '14 at 23:16
  • So there is no limit on recursion then? (by default) – Coffee Maker Jul 22 '14 at 23:18
  • 5
    Python objects are allocated on the heap. The fact that you can create very large integers doesn't tell you anything about the size of the stack, because the amount of stack memory used doesn't depend on the size of the object. – Weeble Jul 22 '14 at 23:22

2 Answers2

8

No modern computer is going to combust due to user code, I promise. Try it for yourself:

def recurseInfinitely( n ):
    recurseInfinitely(n+1)

recurseInfinitely(0)

Running this program promptly yields the output:

  [...]
    recurseInfinitely(n+1)
  File "so.py", line 2, in recurseInfinitely
    recurseInfinitely(n+1)
  File "so.py", line 2, in recurseInfinitely
    recurseInfinitely(n+1)
RuntimeError: maximum recursion depth exceeded

You can catch the error and check the value of n:

def recurseInfinitely( n ):   
    try:
        recurseInfinitely(n+1)
    except RuntimeError:
        print "We got to level %s before hitting the recursion limit."%n

And get:

We got to level 997 before hitting the recursion limit.

Russell Borogove
  • 18,516
  • 4
  • 43
  • 50
3

Python (at least the reference implementation) doesn't - you can't have an infinite recursive loop like in some functional languages. It will throw an exception when recursion reaches around 1000 depth (by default, this can be changed using sys.setrecursionlimit). So yes, the program will crash.

Unlike most functional languages Python lacks tail recursion optimizations. I dare to say that all recursive algorithms should be converted to the iterative form in Python (it is trivial to do so), otherwise your implementation is not really correct.

User larsmans commented that the builtin recursion depth limit is good enough for most practical algorithms, but the iterative form usually performs way better - the reason is that function calls are expensive in Python.

You can have a runway loop in Python if you loop over a generator that never throws StopIteration. It will keep running until (and if) you kill the process or it exhausts computer resources (sometimes grinding the machine to a halt).

Paulo Scardine
  • 73,447
  • 11
  • 124
  • 153
  • In many practical recursive algorithms, recursion depth is logarithmic in the size of the input (think sorting, stable sums). So with the default setting algorithms are correct for at most 2**(1000-c) items for c a small constant. That's correct enough for me. – Fred Foo Jul 22 '14 at 23:31
  • 1
    However, if you're making a library that's expected to handle large amounts of data, iterative is better obviously. I had trouble with a bioinformatics library once that was implemented recursively. >_ – xdhmoore Jan 23 '17 at 05:03