java - 如何在 Python 或 Java 中使这个递归函数更快？

Question

我有这个递归函数: F(n)=4F(n-1)+F(n-2)，对于所有 n>=2，其中 F(0)=0 且 F(1)=1。 这是我在 python 中的代码

def f(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


print f(2424)

Java 中的方法:

static public long f(int n){
    long res = 0;
    if(n==0){
        return 0;
    }else if(n==1){
        return 1;
    }else{
    res=(4*(f(n-1)))+f(n-2);
    }
    return res;
}

我只是在主体中调用它:

public static void main(String[] args) {
    System.out.println("Answer "+f(2424));
}

我必须计算 F(2424)，但它花费了很长时间，以至于 5 小时后程序还没有完成。我想知道我是否做错了什么，或者是否有更好的方法来做到这一点。我对 C、C++ 或 Mathematica 等其他语言持开放态度。我知道它有效，因为它给出了正确的答案。 F(2424) 的答案是一个很大的数字，它是这样的:

12811645111887631525475128340409754383702010324654360624942154540228791340642173492088690105771256884654221447044702819165479281916547925 36437695939355252697103801778677462085188924098182725088076503022685270760387219787300737538930978100645525578032205449176466773 504450636395291929172451449463996726060365432143502604816221037486542202848574347687238119003684559306772150548489964161619741843737 9655349708272370088617205463337763986915180942063012994307233629605426555925124836050521444499111474463839727615711808442476922526 99233890416001827659244246018252661317668176588876191524476644458278180175907595564089578464053541289889658353085449595174445963717445963627 58091873287466207009296604036070639562647289572000261822425465089043313656573939569536654054677090750218737467173010106881247848350 1470060709922311143096204137977283053639448572312486337772156811780487145559605832857694232695773470923184525979593764852986848060 714523588395850662909318298227582307310778309451672655308099393781174736252795563172674626472496404368906252690885379237183783856 260655070865943548153644344223675889074029046747642373676259642885893016853991889034142604989137412360248691074841965206887876419191 92341956202251387111284959021026187364250150290025209285583681567226202086003832311810035678663863088043523641204094317173758585501 40072702579610201398332444667655843894415660856081122556945790699471646832

还是我只需要等待一个非常繁重的程序？

Answer 1

让我们看一个示例 n == 5，它将调用 f(4) 和 f(3)。这些依次调用 f(3)、f(2)、f(2) 和 f(1)。如您所见，有很多多余的评估，当您转到更大的 n 时，这个滚雪球会越来越大。

因此，只需跟踪您已经计算的内容，事情就会大大加快:

def f(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res

def f_all(n):
    res = (n+1)*[0]
    res[1] = 1
    for i in range(2, n+1):
        res[i] = 4*res[i-1] + res[i-2]
    return res

print f(10) == f_all(10)[-1]
print f_all(2424)[-1]

更新:无法抗拒添加高科技解决方案。它使用数学势利者称之为环 Z[sqrt(5)] 的矩阵表示来评估封闭形式的解决方案。这是必要的，因为如果 n 很大， float 就不够准确。

def f_high_tech(n):
    import numpy as np
    powpow2_p = np.array([[2, 1], [5, 2]], dtype=object)
    power_p_n = np.identity(2, dtype=object)
    while n > 0:
        if n&1:
            power_p_n = np.dot(power_p_n, powpow2_p)
        powpow2_p = np.dot(powpow2_p, powpow2_p)
        n >>= 1
    return power_p_n[0, 1]

print f(10) == f_all(10)[-1]
print f_all(2424)[-1] == f_high_tech(2424) 
print f_high_tech(1<<20).bit_length()