python - 如何找到解决这个大值递归问题的数学方法呢？

Question

带有递归函数的python代码。计算这个就是PC变慢了。那么有没有一种简单的方法可以找到这段python代码的答案呢？

def rec(n):
    if n<1:
      return 1
    return rec(n//4)+rec(n//2)
print(rec(12345678987654321))

Answer 1

您可以考虑扩展递归关系，或者您可以简单地使用 memoization :

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def rec(n):
    if n<1:
      return 1
    return rec(n//4)+rec(n//2)

print(rec(12345678987654321))

上面的代码在我的电脑上需要大约 30 毫秒，包括启动 Python 解释器所花费的时间。

记忆化通过不为相同的 n 值多次计算 rec() 来加快速度(原始版本一遍又一遍地重复相同的计算，浪费了大量的 CPU 周期)。