英文:
Why does this code work on Python 3.6 but not on Python 3.7?
问题
在 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 正确打印 f(400)，但在 python3.7 script.py 中会发生堆栈溢出。在3.6中，递归深度在 f(501) 处达到上限，在3.7中则在 f(334) 处达到上限。
Python 3.6 和 3.7 之间发生了什么变化，导致这段代码在3.7中更早地达到了最大递归深度？
英文:
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?
答案1
得分: 8
在对比 Python 3.6.0b1 和 Python 3.7.0a1 之间进行了一些 git 的二分查找后，我发现了 bpo bug #29306（git 提交 7399a05，620580f），它指出了递归深度计数存在一些问题。
最初，Victor Stinner 报告说他不确定一些新的内部 API 函数是否正确处理了递归计数，这些函数是为了优化调用而引入的（属于报告的调用开销优化的一部分），但经过进一步讨论，决定问题更普遍，所有对 C 函数的调用都需要正确处理递归计数。
链接问题中包含了一个简单的测试脚本，演示了在较旧的 Python 版本中存在递归计数问题；该脚本依赖于开发树中的一个特殊扩展模块。然而，尽管已经证明 Python 版本 2.7、3.5 和 3.6 受到了影响，但这些更改从未被反向移植。我猜测这可能是因为这些版本没有接受调用开销优化的反向移植会涉及大量工作。我还在 Python 更改日志中找不到这个更改的条目，也许是因为 Victor 认为这是优化工作的一部分。
这些更改意味着 sum() 和其他内置函数现在会计入递归调用限制，而之前并非如此。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论