如何利用数组加速递归？大参数递归计算耗时过长求助

我尝试优化这段递归代码的运行速度，但当输入参数z=50、x=44.4时，代码运行耗时过长。该参数下的预期输出为-800555.6302016332。

原代码如下：

z = int(input())
x = float(input())

def rec(n):
    global x
    l = {}
    if n == 0:
        return -1
    elif n == 1:
        return x
    elif n == 2:
        return -(x+1)/3
    else:
        if n in l:
            return l[n]
        value = float((n/x)*rec(n-1) + ((-1)**n)*((n+1)/(n-1)) * rec(n-2) + ((n-1)/(2*x))*rec(n-3)) 
        l[n] = value
        return value
print(rec(z))

问题分析 #

原代码的核心问题是缓存完全失效：缓存字典l定义在函数rec内部，每次调用rec都会创建新的空字典，根本没起到缓存已计算结果的作用，导致大量重复递归计算，这是z=50时耗时过长的直接原因。

优化方案 #

方案1：使用functools.lru_cache装饰器（推荐） #

利用Python内置的缓存装饰器自动缓存函数调用结果，无需手动维护缓存，同时规避全局变量的弊端：

from functools import lru_cache

z = int(input())
x = float(input())

@lru_cache(maxsize=None)
def rec(n, x_val):
    if n == 0:
        return -1.0
    elif n == 1:
        return x_val
    elif n == 2:
        return -(x_val + 1) / 3
    else:
        # 用条件判断替代幂运算，小幅提升性能
        sign = 1 if n % 2 == 0 else -1
        value = (n / x_val) * rec(n-1, x_val) + sign * ((n+1)/(n-1)) * rec(n-2, x_val) + ((n-1)/(2*x_val)) * rec(n-3, x_val)
        return value

print(rec(z, x))

方案2：手动维护全局缓存字典 #

将缓存字典移到函数外部，确保所有递归调用共享同一个缓存空间：

z = int(input())
x = float(input())

cache = {}

def rec(n):
    global x, cache
    if n in cache:
        return cache[n]
    if n == 0:
        res = -1.0
    elif n == 1:
        res = x
    elif n == 2:
        res = -(x + 1) / 3
    else:
        sign = 1 if n % 2 == 0 else -1
        res = (n / x) * rec(n-1) + sign * ((n+1)/(n-1)) * rec(n-2) + ((n-1)/(2*x)) * rec(n-3)
    cache[n] = res
    return res

print(rec(z))

优化效果 #

两种方案都能彻底避免重复计算，调用rec(50, 44.4)时会瞬间得到预期输出-800555.6302016332。

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