为什么这段代码在 Python 3.6 上可以运行但是在 Python 3.7 上无法运行？

Question

在 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 之间发生了什么变化，导致此代码的最大递归深度提前超过了限制？

- wim

---

与https://dev59.com/9ddmpIgBRmDukGFEUB8L#75974020相关。 - Samwise

@msi_gerva 首先执行f(100)可以预先填充共享缓存，避免超出堆栈限制，从而减少对后续调用f(400)的递归深度。 - chepner

每个版本中触发RecursionError所需的最小值是多少？我不确定如何负责，但3.7是第一个具有新的键顺序保留实现的(C)Python版本。 - chepner

这是一个很好的问题，因为你可以认为这是一种倒退（即使只是在某种未知情况下有效堆栈缩短了33%）, 而且需要一些时间才能注意到。 - chepner

尝试在两个版本中使用此链接。缩小的演示，自制的sum和自动限制搜索。在我的测试中，自制的sum似乎有所不同，将Python 3.6的限制降低到333 这里。所以看起来是关于sum的某些变化。但我不知道如何进一步查找... - Kelly Bundy

Answer 1

在Python 3.6.0b1和Python 3.7.0a1之间进行了一些git bisect操作后，我发现了bpo bug #29306（git commits 7399a05, 620580f），它指出了递归深度计数的一些错误。

最初，Victor Stinner报告说他不确定一些新的内部API函数用于优化调用（作为报告中的调用开销优化的一部分）是否正确处理了递归计数器，但经过进一步讨论后，决定问题更普遍，所有对C函数的调用也需要正确处理递归计数器。

在链接的问题中包含了一个简单的测试脚本，证明旧版本的Python也存在递归计数的问题；该脚本依赖于开发树中的特殊扩展模块。然而，尽管已经证实Python 2.7、3.5和3.6版本受到影响，但这些更改从未被回溯。我猜想，因为这些版本没有接收到调用开销优化的回溯，所以回溯工作将会非常繁重。我也找不到这个变化在Python changelog中的记录，可能是因为Victor认为这是优化工作的一部分。

这些更改意味着sum()和其他内置函数现在会计入递归调用限制，而之前则不会。

- Martijn Pieters