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

Question

在this video通过Mathologer上，除其他事项外，无限的款项有在9:25出3和不同的无限资金，当视频突然冻结和大象diety弹出，挑战观众发现的“可能的值”表达式。我写了下面的脚本随着精度逼近最后的三个（即1 + 3 .../2 ...）：

from decimal import Decimal as D, getcontext # for accurate results 

def 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 necessary 

for x in range(1, 31): 
    DEPTH = x 
    print(x, main(0)) 

现在这个工作完全罚款1 < = x < = 20ish，但在此之后它开始为每个结果永恒。我意识到这是由于每个DEPTH级别的函数调用数量呈指数级增长。同样清楚的是，我无法轻松地将系列计算到任意点。然而，在该程序减慢一点对于我来说太早清楚地识别限制它汇聚成系列（这可能是1.75，但是我需要更多的DEPTH是一定的）。

我的问题是：如何获得尽可能多的从我的脚本越好（性能明智）？

我曾尝试：
1.找到数学解决这个问题。 （无匹配结果）
2.寻找优化递归函数的方法。根据多个来源（例如this），Python默认情况下并未优化尾递归，所以我尝试切换到迭代样式，但我几乎立即想出了如何实现这一点...

任何帮助感谢！

注：我知道我可以去了解这个数学上，而不是“暴力破解”的限制，但我想我的程序运行良好，现在我已经开始......

Answer 1

你可以的run1，run2和run3功能结果存储在阵列中，以防止他们在你的例子被重新计算每一次，因为main(1)调用run1(1)，它调用run3(2)和run2(2)，这反过来又调用run1(3)，run2(3)，run1(3)（再次）和run3(3)等等。

你可以看到，run1(3)被称为两次评估，而这只会随着数量的增加恶化;如果我们算上次，每次函数被调用的次数，这些都是结果：

run1 run2 run3 
1 1 0 0 
2 0 1 1 
3 1 2 1 
4 3 2 3 
5 5 6 5 
6 11 10 11 
7 21 22 21 
8 43 42 43 
9 85 86 85 
    ... 
20 160,000 each (approx.) 
    ... 
30 160 million each (approx.) 

这实际上是帕斯卡三角的变体，你可以可能图出来的结果数学;但由于您在这里要求进行非数学优化，请注意呼叫数量是如何呈指数增长的;它在每次迭代中都会翻倍。这更糟糕，因为每个呼叫都会产生数千个具有更高值的后续呼叫，这是您想要避免的。

因此，你想要做什么是存储每个呼叫的价值，从而使功能并不需要被调用一千次（和本身使数以千计的电话）总是得到相同的结果。这被称为memoization。

这里是伪代码示例解决方案：

before calling main, declare the arrays val1, val2, val3, all of size DEPTH, and fill them with -1 

function 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在添加注释，你可以保持你原来的代码，只需您的每一个run1，run2和run3功能，其中n是两个以上深度的第一强国之一，以前添加@lru_cache(maxsize=n)（用于例如，如果深度为25，则为32）。这可能需要导入指令才能工作。

Answer 2

对于某些记忆化，你可以起床堆栈溢出：

from decimal import Decimal as D, getcontext # for accurate results 

def main(c): # faster code when functions defined locally (I think) 
    mrun1 = {} # store partial results of run1, run2 and run3 
       # This have not been done in the as parameter of the 
       # run function to be able to reset them easily 

    def run1(c): 
     if c in mrun1: # if partial result already computed, return it 
      return mrun1[c] 

     c += 1 
     if c <= DEPTH: 
      v = D(1) + run3(c)/run2(c) 
     else: 
      v = D(1) 

     mrun1[c] = v # else store it and return the value 
     return v 

    def run2(c): 
     if c in mrun2: 
      return mrun2[c] 

     c += 1 
     if c <= DEPTH: 
      v = D(2) + run2(c)/run1(c) 
     else: 
      v = D(2) 

     mrun2[c] = v 
     return v 

    def run3(c): 
     if c in mrun3: 
      return mrun3[c] 

     c += 1 
     if c <= DEPTH: 
      v = D(3) + run1(c)/run3(c) 
     else: 
      v = D(3) 

     mrun3[c] = v 
     return v 

    return run1(c) 

getcontext().prec = 150 # too much precision isn't currently necessary 

for x in range(1, 997): 
    DEPTH = x 
    print(x, main(0)) 

Python会堆栈溢出，如果你去了997