如何在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;
}

我只是在 main 中调用它：

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

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

12811645111887631525475128340409754383702010324654360624942154540228791340642173492088690105771256884654221447044702887147589907921153496166236437695939355252697103801778677462085188924098182725088076503022685270760387219787300737538930978100645525578032205449174673556667517367894515395044506363952919291724514494639967260603654321435026048162210374865422028485743476872381190036845593067721505484899641669193471741435203077087818965534970827237008861720546333776398691518094206301299430723362960542655592512483605052144449911147446383972761571180832477426059987410922498622599233890416001827659244246018252661317668176588876191524476644458278180175907595564089578464053541289889658353085449595345638114956277894377440265809187328746620700929660403607063956264728957200026182242546508904331365657393956953665405467709075021873746717301068844742812640804898358450341147006070992231114309620413797728305363944857231248633777215681178048714555960583285769423269577347092318452597959376442984898597806086880665642171452358839585066290931829822758230731077830945167265530809939378117473625279556317267462647249640436890625269088579237115076783934027795187388832606550708659435481536443442236758890740290467476423736762596428858930168539918890341426049891374123602486910741965206888619217749898476459891203923419562022513871112849590210261873642501502900252092855836815672262020860038323118100356786638630880435236412040943537555010407001968832788551740072702579610201398332444667655843894415660856081122556945790699471646832

或者这只是一个非常繁重的程序，我只能等待？

Answer 1

让我们看一个n == 5将调用f(4)and的示例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 很大，浮点数就不够准确。

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()