Why does eval consume twice the recursion limit?

Question

The question is: What is the difference between eval() and another functions which don't so massively fill the call stack? That eval() and exec() seem to differ from the other builtin functions and own functions in relation to stack space need is stated already in the question, so an answer that it is because it is that way is confirmation of the fact, but not an explanation why?

I am aware of Why Python raises RecursionError before it exceeds the real recursion limit? question, but the answers there don't apply to following case:

from sys import getrecursionlimit
print(f'sys: maxRecursionDepth = {getrecursionlimit()}')
cnt = 0
def f3(s):
    global cnt
    cnt += 1
    eval(s)
# ---
try:
    f3('f3(s)')
except RecursionError:
    print(f'f3() maxRecursionDepth =  {cnt}')

which outputs:

sys: maxRecursionDepth = 1000
f3() maxRecursionDepth =  333

It seems that calling eval() consumes two recursion levels before the counter in the recursive function is increased again.

I would like to know why is it that way? What is the actual deep reason for the observed behavior?

The answers in the link above don't apply here because they explain that the stack might be already used by other processes of Python and therefore the counter does not count up to the recursion limit. This does not explain: What is the difference between eval()/exec() and another functions which don't so massively fill the call stack? I would expect a 499 or similar as result, but not 333 out of 1000.

Answer 1

Each eval call needs two stack levels:

• The execution of eval itself.
• The execution of eval's argument.

While eval is a builtin, the ()-call does not know that ahead of time – it cannot be "inlined" and still needs a stack level to execute. The argument is executed as a separate statement with the given or implicit globals/locals, and thus also needs a stack level.

The sneaky part is that eval prevents re-using the current call to f3(…) to execute the statement for its next call. The added top-level is visible when not suppressing RecursionError:

...
  File "/Users/mistermiyagi/so_testbed.py", line 7, in f3
    eval(s)
  File "<string>", line 1, in <module>
  File "/Users/mistermiyagi/so_testbed.py", line 7, in f3
    eval(s)
  File "<string>", line 1, in <module>
...

Each File "<string>", line 1, in <module> is a separate frame for the top-level execution. The eval execution itself does not show up since it is a builtin call and thus has no Python frame, only a C stack level.

---

Let's look at a simpler example without the complications of counting recursions:

def direct():
    direct()

def via_eval():
    eval("via_eval()")

We can call each of those directly; the stack trace then reveals the Python frames involved.

• The direct call shows just the direct frames. The stack thus looks like this:

  … -> direct() -> direct() -> …
  

• The via_eval call also shows the File "<string>", line 1, in <module> frames; while eval has no frame we know it is called. The stack thus looks like this:

  … -> via_eval() -> eval() -> <module> -> via_eval() -> eval() -> <module> …
  

This is why the stack level – and thus the speed at which we hit recursion limit – increases by factor 3 instead of 2.

To understand why eval() needs a separate <module>, we can look at a related concept: eval is to calls what functions are to code.

# equivalent to def eval(code): …
def call(func):
    func()

def via_call():
    # equivalent to eval("via_call()")
    call(lambda: via_call())

This is a 1:1 translation of the via_eval setup. The traceback¹ equally shows that the helper that performs the execution is separate from the helper being executed.

  … -> via_call() -> call() -> <lambda> -> via_call() -> call() -> <lambda> …

Just like call here triggers the execution of something else (a function) eval also triggers the execution of something else (a code object). Since the trigger (call/eval) and the triggered (lambda: via_call())/'via_eval()') are separate things each needs its own stack level.

---

¹

  File "/Users/mistermiyagi/so_testbed.py", line 6, in via_call
    call(lambda: via_call())
  File "/Users/mistermiyagi/so_testbed.py", line 2, in call
    func()
  File "/Users/mistermiyagi/so_testbed.py", line 6, in <lambda>
    call(lambda: via_call())

Answer 2

The "recursion" limit doesn't actually care about recursion. It cares about how many stack frames you create. If you set it to something really low, you can trigger RecursionError without recursion.

>>> import sys
>>> sys.setrecursionlimit(4)
>>> def a():
...   b()
...
>>> def b():
...   print("Never here")
...
>>> a()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in a
  File "<stdin>", line 2, in b
RecursionError: maximum recursion depth exceeded while calling a Python object

In your case, it's the call to eval at each step that causes you to fill the call stack sooner than you expect.