Python中如何优化存在重复递归调用的函数执行效率

核心问题说明 #

原代码中同一层级递归调用了两次f(n-1)，相当于对每个n的子问题重复计算了两次，时间复杂度为指数级，可通过以下方案优化：

优化方案1：单次计算复用结果（最小改动） #

直接把f(n-1)的计算结果暂存到局部变量，避免同一递归层级的重复计算，改动最小，改完后递归时间复杂度直接降到O(n)

def f(n):
    if n == 1:
        return 1
    else:
        # 只计算一次f(n-1)，复用结果
        res_prev = f(n-1)
        return (1 / (n - 1)) * (res_prev + (1 / res_prev))


n = int(input())
print(str(round(f(n),2)))

优化方案2：添加记忆化缓存（适配多调用场景） #

如果业务场景会多次调用不同n的f函数，可以加装饰器做结果缓存，避免跨调用的重复计算：

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
    if n == 1:
        return 1
    else:
        res_prev = f(n-1)
        return (1 / (n - 1)) * (res_prev + (1 / res_prev))


n = int(input())
print(str(round(f(n),2)))

优化方案3：改为迭代实现（避免递归栈溢出） #

当n的值非常大的时候，递归实现会触发Python的递归深度限制报错，改成迭代实现不仅完全没有重复计算，还能规避栈溢出问题，效率最高：

def f(n):
    res = 1  # n=1时的结果
    for i in range(2, n+1):
        res = (1 / (i - 1)) * (res + 1 / res)
    return res


n = int(input())
print(str(round(f(n),2)))

内容的提问来源于stack exchange，提问作者J.Guo