为什么在python中迭代次数越多，递归函数的执行时间平均越快？

Question

我正在比较python中两个不同函数的速度。它们是某些通用算法的两个实现，其中一个是递归的，另一个使用堆栈

当使用time和timeit查看单个迭代的速度时，递归实现大约慢40倍。这是意料之中的，因为递归相对较慢

但是，当我使用time和timeit运行1000000次迭代时，递归实现完成所有这些迭代所花费的时间仅比堆栈实现慢30%

这对我来说毫无意义。我使用time的原因是在对递归函数计时时检查timeit是否正常工作，因为我认为一定有错误

需要注意的是，我确保在对每个函数计时时使用相同的迭代次数。我也多次运行这些计时，我仍然得到相同的结论

有没有任何潜在的原因来解释为什么更多的时间迭代导致这个递归算法在速度上与非递归版本非常接近

不幸的是，我无法显示实现代码。我不需要一个明确的答案，我只是想知道为什么会这样。然而，这是你的基本要求

iterationNum=100000
print(timeit.timeit(recursiveImplementation, number=iterationNum))
print(timeit.timeit(stackImplementation, number=iterationNum))

Answer 1

如果您看到测试1次迭代和1000次迭代之间的巨大差异，那么递归函数很可能使用了某种形式的内存化（保存在全局变量中），从而加快了后续调用的速度。请记住，一个可变的默认参数也可能最终得到一个全局范围。无论如何，递归实现肯定会产生副作用，影响后续调用