如何提升Python递归函数速度？解决其运行过慢或无结果问题

你的递归函数本质是类似斐波那契数列的递推结构，但指数级的重复计算是导致运行极慢的核心原因——每次计算x(a)都会重复计算x(a-1)、x(a-2)以及它们的所有子问题，比如x(5)会触发x(4)和x(3)，而x(4)又会再次触发x(3)和x(2)，随着a增大，重复计算量呈爆炸式增长。以下是几种高效的修复方案：

方案1：添加记忆化缓存 #

利用Python内置的functools.lru_cache装饰器缓存已经计算过的结果，避免重复计算，时间复杂度直接降到O(n)：

from functools import lru_cache

@lru_cache(maxsize=None)
def x(a):
    return x(a - 1) + x(a - 2) + 42 if a > 1 else a

print(x(195))

也可以手动用字典实现缓存，适合不想引入装饰器的场景：

cache = {}
def x(a):
    if a in cache:
        return cache[a]
    if a <= 1:
        res = a
    else:
        res = x(a - 1) + x(a - 2) + 42
    cache[a] = res
    return res

print(x(195))

方案2：改用迭代实现 #

递归调用本身有一定的栈开销，迭代可以彻底避免递归栈的潜在问题，同时空间复杂度优化到O(1)：

def x(a):
    if a <= 1:
        return a
    prev_prev = 0  # x(0)
    prev = 1       # x(1)
    for i in range(2, a + 1):
        current = prev + prev_prev + 42
        prev_prev, prev = prev, current
    return prev

print(x(195))

方案3：推导通项公式（数学优化） #

原递推式是线性非齐次递推关系，可推导通项公式直接计算结果：

当a>1时，x(a) = x(a-1) + x(a-2) + 42；x(0)=0，x(1)=1

推导后得到的通项公式实现如下（利用浮点数计算后取整，精度足够覆盖a=195的场景）：

import math

phi = (1 + math.sqrt(5)) / 2
psi = (1 - math.sqrt(5)) / 2

def x(a):
    if a <= 1:
        return a
    A = (43 + math.sqrt(5)) / math.sqrt(5)
    B = (43 - math.sqrt(5)) / (-math.sqrt(5))
    return round(A * (phi ** a) + B * (psi ** a) - 42)

print(x(195))

内容的提问来源于stack exchange，提问作者Hahan't