如何优化嵌套递归函数 解决Excel转Python时的递归效率问题

问题背景 #

我正在将复杂的Excel表格逻辑转换为Python代码，以下是该Excel表格的简化示例：

r       a               b          c            d
1       2%             a(r)+1   b(r)*2+a(r)   100
2to100  d(r-1)*.0001   a(r)+1   b(r)*2+a(r)   d(r-1)*c(r)

最初编写的实现代码如下：

def a(r):
  if r==1:
    return 0.02
  else:
    return d(r-1)*0.0001
def b(r):
  return a(r)+1
def c(r):
  return b(r)*2+a(r)
def d(r):
  if r==1:
    return 100
  else:
    return d(r-1)*c(r)

性能问题 #

当前简化示例理论上可以不用单独定义a、b、c函数，合并为一个递归函数即可，但真实场景下的表格逻辑非常复杂，合并的工作量极高。
分开编写多个递归函数会出现严重的重复调用问题：每一步计算中a函数会被重复调用3次，调用d(100)的操作等价于调用a函数3^{100≈5.1×10}47次，完全无法完成运行，需要在不改动现有分函数结构的前提下，让每一步的a函数仅被调用一次。

优化方案 #

给递归函数添加lru_cache缓存装饰器即可解决重复计算问题，优化后d(100)的运行时间可缩短到1秒以内，优化后的代码如下：

from functools import lru_cache
@lru_cache(maxsize = 128)
def a(r):
  if r==1:
    return 0.02
  else:
    return d(r-1)*0.0001
def b(r):
  return a(r)+1
def c(r):
  return b(r)*2+a(r)
def d(r):
  if r==1:
    return 100
  else:
    return d(r-1)*c(r)/3

优化原理 #

lru_cache会自动缓存函数的入参和对应的返回结果，同一个入参第二次调用函数时会直接返回缓存的结果，不会重复执行函数逻辑。本场景下每个r值对应的a(r)只会被计算一次，后续所有调用都直接取缓存结果，从根源上避免了指数级的重复计算。

内容的提问来源于stack exchange，提问作者Walterwang201112