Why does Python have a maximum recursion depth?

by

There are actually a few issues here.

First, as NPE’s answer nicely explains, Python doesn’t eliminate tail calls, so many functions that would allow unlimited recursion in, say, Scheme are limited in Python.

Second, as again as explained by NPE, calls that can’t be eliminated take up space on the call stack. And, even in languages that do TCE, there are plenty of recursive functions that can’t be treated like iteration. (Consider the naive Fibonacci function that recursively calls itself twice.)

But why is the call stack a finite resource in the first place? Python stack frames can at least in principle be implemented on the heap and linked together (see Stackless for an existence proof of that principle), and in a 64-bit memory space, there’s room for a whole lot more than 1000 stack frames. (In fact, even the C stack on almost any modern platform can hold a whole lot more than 1000 recursive Python interpreter calls.)

Part of the reason is historical: the stock Python interpreter uses the fixed C stack to call itself recursively whenever you make a recursive call, and it was originally designed for 32-bit (and even 24- or 20-bit) platforms where that C stack is pretty small.

But that could have been changed, and Python 3.0 would have been a perfect place to change it. So, why didn’t they? Because they made a conscious language design decision. In Pythonic code, recursion is generally very shallow (e.g., code like os.walk that traverses shallow tree structures); if your function hits a depth of anywhere near 1000, it’s more likely to be a bug than to be intentional. So, the limit stays. Of course this is a bit circular—if they removed the limit (and, especially, if they eliminated tail calls), deeper recursion would become more idiomatic. But that’s kind of the point—Guido doesn’t want a language where deep recursion is idiomatic. (And most of the Python community agrees.)

More Related Contents:

  1. Does Python optimize tail recursion?
  2. Why does this recursion return 0?
  3. One line recursive loop in python
  4. Nested defaultdict of defaultdict
  5. Recursive code returns None [duplicate]
  6. How to do a recursive sub-folder search and return files in a list?
  7. Finding a key recursively in a dictionary
  8. How can I build a recursive function in python? [duplicate]
  9. Can a lambda function call itself recursively in Python?
  10. Function with varying number of For Loops (python)
  11. Setting stacksize in a python script
  12. Hitting Maximum Recursion Depth Using Pickle / cPickle
  13. Python recursion permutations
  14. Search for a key in a nested Python dictionary
  15. Python recursive function error: “maximum recursion depth exceeded” [duplicate]
  16. Recursion applied to lists vs trees in Python
  17. Can generators be recursive?
  18. Recursion using yield
  19. Don’t show Python raise-line in the exception stack
  20. python ctype recursive structures
  21. Counting recursive calls of a function
  22. Flattening a list recursively [duplicate]
  23. Is there a recursive version of the dict.get() built-in?
  24. Recursive generator for flattening nested lists
  25. Python recursive function to display all subsets of given set
  26. Valid characters in a String
  27. getattr and setattr on nested subobjects / chained properties?
  28. How to constuct a column of data frame recursively with pandas-python?
  29. What is the maximum recursion depth, and how to increase it?
  30. Max recursion is not exactly what sys.getrecursionlimit() claims. How come?

Leave a Comment