Why does this code work on Python 3.6 but not on Python 3.7?

Question

In script.py:

def f(n, memo={0:0, 1:1}):
    if n not in memo:
        memo[n] = sum(f(n - i) for i in [1, 2])
    return memo[n]

print(f(400))

python3.6 script.py correctly prints f(400), but with python3.7 script.py it stack overflows. The recursion limit is reached at f(501) in 3.6 and at f(334) in 3.7.

What changed between Python 3.6 and 3.7 that caused the maximum recursion depth to be exceeded earlier by this code?

Works with IPython based on Python 3.9.16, but not with ordinary Python 3.9.16 :|... Actually, if I first do print(f(100)), then afterwards works also with f(400). Really strange behaviour. — msi_gerva, Apr 10 '23 at 18:29
Related to https://stackoverflow.com/questions/75973613/can-you-explain-this-difference-of-depth-recursion-in-python-using-those-seeming/75974020? — Samwise, Apr 10 '23 at 18:32
@msi_gerva Doing `f(100)` first pre-populates the shared cache without hitting the stack limit, reducing the recursion depth of the subsequent call to `f(400)`. — chepner, Apr 10 '23 at 19:02
What's the minimum value of `n` required to trigger the `RecursionError` in each version? I'm not sure *how* this would be responsible, but the 3.7 was the first version of (C)Python with the new key-order-preserving implementation of `dict`. — chepner, Apr 10 '23 at 19:07
Partial duplicate: [Why Python raises RecursionError before it exceeds the real recursion limit?](/q/55560258/4518341) That still leaves the question of why the behaviour changed in 3.7. — wjandrea, Apr 10 '23 at 20:09
On that note, maybe people are downvoting because you're asking about an outdated Python version? Doesn't make much sense, but just a guess. — wjandrea, Apr 10 '23 at 20:10
It's a good question, because you could consider this a regression (even if only one that took a while to notice) in the stack being effective 33% shorter in some unknown circumstance. — chepner, Apr 10 '23 at 20:14
Try [this](https://ato.pxeger.com/run?1=TZA7DsIwDIb3nMJjKlQJNorUkQuwog6lTSACnMp1pPYsLF3gThyCO4D7oPVm___n1-NVtXzx2HXPwDbevj-lsWA1RjsFvyDDgRAQciyhDndttYvAegIHDuGI8SaLlBJIVMd_rg43hhTWfSpAI4DjQV94Vik0y1lDWSlhUBjK8Wx0kiRjb6Z2biKr9olpClMxHEwRqHYe90SeZl9FDnnySpzI5Nfh6PH26Qdf) in both versions. Minified demo, selfmade `sum`, and automatic limit search. The selfmade-sum seems to make the difference, drops the limit to 333 for Python 3.6 in my testing [here](https://www.jdoodle.com/python3-programming-online/). So looks like something about `sum` changed. But I don't know how to look further... — Kelly Bundy, Apr 12 '23 at 19:49
@chepner older Python versions did not handle the recursion counter correctly but the bugfix was never backported to 3.6. — Martijn Pieters, Jun 11 '23 at 17:54

Martijn Pieters · Accepted Answer · 2023-06-11T21:11:48.253

After some git bisecting between Python 3.6.0b1 and Python 3.7.0a1 I found bpo bug #29306 (git commits 7399a05, 620580f), which identified some bugs with the recursion depth counting.

Originally, Victor Stinner reported that he was unsure that some new internal API functions for optimised calls (part of the reported call overhead optimisations) were handling the recursion counter properly, but after further discussion it was decided that the problem was more general and that all calls to C functions need to handle the recursion counter too.

A simple test script is included in the linked issue that demonstrates that there are issues with recursion counting in older Python versions too; the script depends on a special extension module that is part of the development tree. However, even though Python versions 2.7, 3.5 and 3.6 were shown to be affected the changes were never back-ported. I'm guessing that because those versions didn't receive the call overhead optimisations backporting was going to be a lot of work. I also can’t find an entry for this change in the Python changelog, perhaps because Victor regarded this as part of the optimisation work.

The changes mean that sum() and other built-in functions now count against the recursive call limit where they didn’t before.

Why does this code work on Python 3.6 but not on Python 3.7?

1 Answers1

Linked