如何找到一个数学方法来解决这个大值递归问题？

Question

带有递归函数的python代码。要计算这一点，PC会减慢速度。那么有没有一种简单的方法来找到这个python代码的答案呢？你知道吗

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

Answer 1

您可以使用lru_cache模块中的functools。
https://docs.python.org/3/library/functools.html
如文件所述

Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments

如果将maxsize设置为None，则缓存将不受限制地增长。你知道吗

from functools import lru_cache

@lru_cache(maxsize = None)
def rec(n):
    if n < 1:
        return  1
    return rec(n // 4) + rec(n // 2)
print(rec(12345678987654321))

时间度量：

times = timeit.timeit(setup = 'from __main__ import rec',
stmt = 'print(rec(12345678987654321))', number = 1)

与lru_cache

225851433717
0.00023956200311658904

没有lru_cache

More than 2 minutes