-1

Currently python has a recursion depth of 1000 but i am failing to understand why there is a limit since everything in located on the heap.

Memory management in Python involves a private heap containing all Python objects and data structures. The management of this private heap is ensured internally by the Python memory manager

A common way to avoid stackoverflow is to declare your own stack and use a loop but in this case we are already using the heap.Is it a restriction set by python memory management? .

user2650277
  • 6,289
  • 17
  • 63
  • 132
  • Python has a *configurable* recursion *exception* limit. It is a reminder that there is most likely something going wrong. And of cause that you should prevent recursion if possible. (It always is.) – Klaus D. Sep 10 '18 at 18:03
  • "everything is allocated on the heap" is wrong. In CPython, `Frame` objects are allocated on the heap, but recursive calls generally work by recursively calling the `ceval` function with the main interpreter loop. So, unrestricted recursion could lead to a C-level stack overflow, which would be bad. Removing that is what [Stackless](https://github.com/stackless-dev/stackless/wiki) is all about (although it's not as exciting since `greenlets` and then Python 3.3 itself found ways to do coroutines without changing the core interpreter loop). – abarnert Sep 10 '18 at 18:08
  • But even Stackless lets you set a maximum recursion depth, because when you write an unbounded-recursive function, it's nicer to get a `RecursionError` after a couple seconds than to drive your system into swap hell so everything (not just your program) slows to a crawl and takes minutes to recover after you finally get a `MemoryError`. – abarnert Sep 10 '18 at 18:39
  • In a language that encouraged recursion whenever possible, like Scheme, this wouldn't be a good heuristic. But in a language that discourages recursion whenever it's not necessary, like Python, it usually is. – abarnert Sep 10 '18 at 18:42

1 Answers1

2

CPython is implemented in C, and while Python's data is allocated from a heap, layers of native C function calls in the implementation necessarily use the platform C's stack. So, for example, recursive calls of depth R in Python code also lead, at runtime, to calls to C functions of depth at least R in the C implementation.

So it's not primarily about the data, but about the call-stack depth. It's possible to implement Python in C in ways that don't so directly rely on the platform C's call stack. For example, see the "Stackless Python" experiment. That's trickier, though, and it's unlikely the core CPython implementation will ever adopt that kind of approach.

Tim Peters
  • 67,464
  • 13
  • 126
  • 132
  • 1
    Clear and simple to understand even to a beginner programmer like me.Its great to have you on SO and yes timsort is awesome. – user2650277 Sep 10 '18 at 18:17