Why is the number of recursion 9 less than the recursion limit?

Question

I was trying to make recursive function when i came across this problem (not really a problem but i am curious and couldnt find the answer anywhere else). When i run the code, it gives me a recursion error and how many times it repeated before the recursion limit was' exceeded.

[Previous line repeated 91 more times]
RecursionError: maximum recursion depth exceeded

In this case i had set the recursion limit to 100 but the number of times it repeated was 91, similarly if i set the limit to 1000, the error is [Previous line repeated 991 more times]. I assumed this was happening because the first few parts of the stack were being taken up by other parts of the program, so i tried adding the same function to a different peice of code but the recursion is still 9 less. Whys this happening?

Isn't the 'previous line' repeated already about 9 times in the error message itself ? That could be an explanation. If not, then it would mean that the additional calls on the call stack are done by the python interpreter. — m.raynal, Jan 10 '20 at 14:41
Does this answer your question? [Why Python raises RecursionError before it exceeds the real recursion limit?](https://stackoverflow.com/questions/55560258/why-python-raises-recursionerror-before-it-exceeds-the-real-recursion-limit) — ggorlen, Feb 21 '23 at 17:40

score 2 · Answer 1 · answered Jan 10 '20 at 14:35

Despite the wording of the error, the recursion depth does not only apply to recursive calls to a function. It's the size of the call stack. All function calls apply. If you were already 9 calls deep into the stack when you called the recursive function, that would explain you hitting the limit.

Unrelated to your situation, but list comprehensions are implemented in terms of anonymous functions, which also contribute to hitting the limit. For example:

>>> sys.setrecursionlimit(20)
>>> def f():
...   return [f() for _ in range(20)]
...
>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in <listcomp>
  File "<stdin>", line 2, in f
RecursionError: maximum recursion depth exceeded while calling a Python object

Only 10 calls to f, but each list comprehension also used on of the 20 available stack frames.

ShadowRanger · Accepted Answer · 2020-01-10T15:46:25.557

Without seeing your code, we can't say precisely, but there is almost always going to be some number of stack frames created by the code that eventually calls the recursive function that contributes to the cap. If you're in a situation where your recursion is coming that close to the cap already, your code is either broken (infinite, or excessive recursion that simply won't work in Python) or you need to set a significantly higher bound (large enough for your deep, but bounded recursion, plus a reasonable buffer).

For example, even in a bare-bones interactive interpreter session, one level of recursion is covered by the top level call. The recursion deduplication feature also shows the recursive line a few times before it begins collapsing; on my 3.8.0 install, it shows the repeated line three times, then tells me the final copy is repeated 996 more times. Example of a fresh session:

$ python3 -S -E  # -S -E isolates you as much as possible, making plainest interpreter possible
>>> def f(): return f()
...
>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Same behavior occurs for other minimal approaches, e.g. python3 -S -E -c 'f = lambda: f(); f()'. So at least for CPython 3.8.0, at an absolute minimum, you'd expect the count to be four less than the actual recursion limit (the top level frame, plus the first three expanded frames). If you're running in something other than the most basic interpreter (e.g. IDLE, ipython) they are running interactively through layers stacked on the interpreter core, and have more than just the top-level frame automatically. Both of them make an effort to hide this (ipython changes the default recursion limit to 3000 instead of 1000; IDLE seems to do something faintly magical such that the same reproducer above dies while claiming the previous line was repeated 1022 times, even though the recursion limit claims to remain 1000).

You won't see these added layers in the traceback from the RecursionError, because the interpreter wrapper layers catch the exception for display before any of the interpreter stack itself unwinds, and the traceback only shows those frames that were unwound before the exception was caught. You can see these additional layers easily with the traceback module by running (at the same level where you first invoked your overly recursive function) traceback.print_stack(), which, in the case of my ipython3 session, reveals 12 additional frames (excluding the one that actually called traceback.print_stack()). Similarly, my IDLE shows three additional frames hiding above the main prompt. However you're running your code, it's likely running above a base of five stack frames.

Why is the number of recursion 9 less than the recursion limit?

2 Answers2