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.
4
-
possible duplicate of Python max recursion , question about sys.setrecursionlimit()Cory Kramer– Cory Kramer2014-07-22 23:16:09 +00:00Commented Jul 22, 2014 at 23:16
-
Python has a recursion limit that you can set by sys.setrecursionlimit: docs.python.org/2/library/sys.html#sys.setrecursionlimitmgilson– mgilson2014-07-22 23:16:45 +00:00Commented Jul 22, 2014 at 23:16
-
So there is no limit on recursion then? (by default)Coffee Maker– Coffee Maker2014-07-22 23:18:54 +00:00Commented Jul 22, 2014 at 23:18
-
5Python 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– Weeble2014-07-22 23:22:55 +00:00Commented Jul 22, 2014 at 23:22
Add a comment
|
2 Answers
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.
Comments
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).
2 Comments
Fred Foo
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.
xdhmoore
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. >_<