前言
我有一个特定问题的两个实现，一个是递归方法，另一个是迭代方法。我想知道为什么迭代方法比递归方法慢约30%。
给出递归解法后，我写了一个显示栈状态的迭代解法。
显然，我只是模仿递归的做法，因此Python引擎更好地优化了管理。但我们能否编写性能类似的迭代方法呢？
我的案例研究是在欧拉计划中的第14号问题。
找到起始数小于一百万的最长考拉兹数列。
代码
以下是简洁的递归解法（由veritas在问题线程中提供并由jJjjJ进行了优化）：
def solve_PE14_recursive(ub=10**6):
def collatz_r(n):
if not n in table:
if n % 2 == 0:
table[n] = collatz_r(n // 2) + 1
elif n % 4 == 3:
table[n] = collatz_r((3 * n + 1) // 2) + 2
else:
table[n] = collatz_r((3 * n + 1) // 4) + 3
return table[n]
table = {1: 1}
return max(xrange(ub // 2 + 1, ub, 2), key=collatz_r)
这是我的迭代版本：
def solve_PE14_iterative(ub=10**6):
def collatz_i(n):
stack = []
while not n in table:
if n % 2 == 0:
x, y = n // 2, 1
elif n % 4 == 3:
x, y = (3 * n + 1) // 2, 2
else:
x, y = (3 * n + 1) // 4, 3
stack.append((n, y))
n = x
ysum = table[n]
for x, y in reversed(stack):
ysum += y
table[x] = ysum
return ysum
table = {1: 1}
return max(xrange(ub // 2 + 1, ub, 2), key=collatz_i)
在我的电脑上（一台配备大量内存的i7机器）使用IPython，这是时间记录：
In [3]: %timeit solve_PE14_recursive()
1 loops, best of 3: 942 ms per loop
In [4]: %timeit solve_PE14_iterative()
1 loops, best of 3: 1.35 s per loop
评论
递归解法真的很棒：
- 优化可跳过一步或两步，具体取决于最低有效位数。
我的原始解决方案没有跳过任何 Collatz 步骤，并且需要 ~1.86 秒。 - 很难达到 Python 默认的递归限制 1000 次。
collatz_r(9780657630)返回 1133，但递归调用次数小于 1000。 - 备忘录避免了重复追踪
collatz_r长度是按需计算的，针对max
玩弄它时，时间似乎精确到 +/- 5 ms。
像 C 和 Haskell 这样的静态类型语言可以获得低于 100 ms 的时间。
我故意将备忘录 table 的初始化放在方法中，以便此问题反映出在每次调用时 "重新发现" 表值所需的时间。
collatz_r(2**1002) 引发 RuntimeError: maximum recursion depth exceeded。
collatz_i(2**1002) 快乐地返回，其结果为 1003。
我熟悉生成器、协程和装饰器。
我正在使用 Python 2.7。我也很乐意使用 Numpy（在我的机器上是 1.8）。
我所寻找的
- 一个迭代解法，能够缩小性能差距
- 关于 Python 如何处理递归的讨论
- 显式堆栈涉及的性能惩罚的更细节的信息
我主要寻找第一个，尽管第二个和第三个对于这个问题非常重要，并且将增加我对 Python 的理解。
reversed(stack)提示了我。我不记得结果是什么，但稍后我会回报。 - Prashant Kumar