> The dependency of min_limit from new_limit is not monotonic: (...)

Right, _Py_MakeEndRecCheck() is not monotonic.

Let me try to make it monotonic:

def f1(x): return x * 3 // 4
def f2(x): return x - 50

f1() > f2() for x <= 196
f1() == f2() for x in 198..200
f1() < f2() for x > 201

So I propose to switch between f1() and f2() at x>200 for _Py_MakeEndRecCheck(). It gives:

recursion depth => low-water mark

25 => 18
...
50 => 37
...
75 => 56
...
100 => 75
...
125 => 93
...
150 => 112
...
175 => 131
...
198 => 148 -- use f1 (x*3/4)
199 => 149
200 => 150 
201 => 151 -- switch to f2 (x-50)
202 => 152
203 => 153

Attached end_rec_check.patch makes _Py_MakeEndRecCheck() monotonic.