TypedPython: compile recursion (direct and mutual) with CPython's RecursionError #57

What

Compile recursive functions. That covers direct self-calls and mutual recursion between compiled functions. Today the verifier rejects any call cycle, so recursive functions stay interpreted.

Why it is rejected today (safety, not ordering)

1. Stack depth. Compiled C recursion has no depth check. Deep recursion would overflow the C stack and crash the process, where CPython raises RecursionError. That is a memory-safety failure (SPEC N-8), so the verifier refuses it rather than emitting unsafe code.
2. Matching where the error happens. CPython raises RecursionError for Python frames at sys.getrecursionlimit(). Since 3.12, C-level recursion is guarded separately, by stack-pointer checks (Py_EnterRecursiveCall). A compiled frame is neither kind, so the depth at which the error appears has to be specified, not guessed.

Plan (M2b, 2026-11-21)

• Runtime helpers tp_enter_call() / tp_leave_call(), called at every compiled function entry and exit:
  1. C-stack guard. Py_EnterRecursiveCall keeps the process from crashing whatever the limit settings are.
  2. Depth counter. A per-thread count of compiled frames, added to the thread's current Python frame depth and compared with sys.getrecursionlimit(). Hitting the limit raises RecursionError('maximum recursion depth exceeded'), so a recursion made of compiled frames fails at the same total depth as interpreted code.
• Verifier: accepts call cycles when every function on the cycle uses the helpers; the back end always emits them. Cycles through a may_deopt callee stay legal only inside pure functions, as now. A deopt redoes the outermost compiled call, which is safe because it is pure.
• Differential tests:
  • fib, ackermann and mutual is_even/is_odd give the same results as interpreted;
  • recursion past the limit raises RecursionError in both, with the same message;
  • a pure recursive int function that overflows i64 deopts and returns the big int.
• Gap to measure, not assume: how exactly the depth matches when interpreted and compiled frames are mixed, because the Python frame depth is read through public API only. If it cannot be matched exactly, the test records the offset and the design note states it.

Done when

The differential tests pass. binary-trees (M2b) compiles its recursive make_tree/check_tree, and skipped no longer lists recursion for them.