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?
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.