python - Python-如何提高复杂的递归函数的效率？

在Mathologer的this video中，除其他外，无穷和在9:25处显示3种不同的无穷和，这时视频突然冻结，并且突然弹出大象饮食，向观看者发出挑战，要求他们找到该视频的“可能值”表达式。我编写了以下脚本，以提高精度近似了三个脚本中的最后一个（即1 + 3 ... / 2 ...）：from decimal import Decimal as D, getcontext # for accurate resultsdef main(c): # faster code when functions defined locally (I think) def run1(c): c += 1 if c <= DEPTH: return D(1) + run3(c)/run2(c) else: return D(1) def run2(c): c += 1 if c <= DEPTH: return D(2) + run2(c)/run1(c) else: return D(2) def run3(c): c += 1 if c <= DEPTH: return D(3) + run1(c)/run3(c) else: return D(3) return run1(c)getcontext().prec = 10 # too much precision isn't currently necessaryfor x in range(1, 31): DEPTH = x print(x, main(0))现在，这对于1 x DEPTH级别进行的函数调用数量呈指数增长。同样很明显，我将无法舒适地计算出任意点的序列。但是，对于我来说，程序变慢的时间还为时过早，无法清楚地确定其收敛到的序列极限（可能是1.75，但我需要更多的DEPTH来确定）。我的问题是：如何从脚本中获得尽可能多的收益（在性能方面）？我试过了： 1.找到这个问题的数学解决方案。 （没有匹配结果） 2.找到总体上优化递归函数的方法。根据多种来源（例如this），Python默认情况下不会优化尾递归，因此我尝试切换为迭代样式，但是我几乎没有想法几乎立即完成此工作...任何帮助表示赞赏！注意：我知道我可以用数学方法解决这个问题，而不是“强行限制”，但是既然我已经开始，我想让我的程序运行良好。 最佳答案 您可以将run1，run2和run3函数的结果存储在数组中，以防止每次都重新计算它们，因为在您的示例中，main(1)调用run1(1)，而run3(2)调用run2(2)和，依次调用run1(3)，run2(3)，run1(3)和run3(3)，依此类推。您可以看到run1(3)被调用两次，并且只会随着数量的增加而变得更糟。如果我们计算每个函数的调用次数，则结果如下： run1 run2 run31 1 0 02 0 1 13 1 2 14 3 2 35 5 6 56 11 10 117 21 22 218 43 42 439 85 86 85 ...20 160,000 each (approx.) ...30 160 million each (approx.)这实际上是Pascal三角形的一种变体，您可能可以通过数学方法得出结果；但是由于您要求进行非数学优化，因此请注意调用次数是如何呈指数增长的；在每次迭代时都会翻倍。甚至更糟，因为每个调用都会生成数千个具有较高值的​​后续调用，这是您要避免的。因此，您要做的是存储每个调用的值，这样就不必总是调用该函数一千次（并且本身会进行数千次调用），从而始终获得相同的结果。这称为memoization。这是伪代码的示例解决方案：before calling main, declare the arrays val1, val2, val3, all of size DEPTH, and fill them with -1function run1(c) # same thing for run2 and run3 c += 1 if c <= DEPTH local3 = val3(c) # read run3(c) if local3 is -1 # if run3(c) hasn't been computed yet local3 = run3(c) # we compute it val3(c) = local3 # and store it into the array local2 = val2(c) # same with run2(c) if local2 is -1 local2 = run2(c) val2(c) = local2 return D(1) + local3/local2 # we use the value we got from the array or from the computation else return D(1)在这里我使用-1，因为您的函数似乎只生成正数，而-1是空单元格的简单占位符。在其他情况下，您可能需要像我下​​面的Cabu那样使用对象。但是，我认为这样做会比较慢，因为检索对象中的属性要比读取数组的开销大，但我对此可能是错的。无论哪种方式，您的代码现在都应该快得多，花费为O（n）而不是O（2 ^ n）。从技术上讲，这将使您的代码永远以恒定的速度运行，但是递归实际上会导致早期的堆栈溢出。不过，在这种情况发生之前，您可能仍然可以深入到数千个深度。编辑：正如ShadowRanger在注释中添加的那样，您可以保留原始代码，只需在每个@lru_cache(maxsize=n)，run1和run2函数之前添加run3，其中n是DEPTH之上的两个的第一个幂（例如，如果深度为25，则为32）。这可能需要导入指令才能起作用。