比递归更好的方法是记忆。您只需要知道f（n）的最后三个值即可。伪代码的解决方案如下所示：

if n == 0:
    return p
else if n == 1:
    return q
else if n == 2:
    return r
else:    
    f_n-3 = p
    f_n-2 = q
    f_n-1 = r
    for i from 3 to n:
        f_new = a * f_n-1 + b * f_n-2 + c * f_n-3 + g(n)
        fn-1 = fn-2
        fn-2 = fn-3
        fn-3 = f_new

return f_new

这样，您无需递归调用该方法并将所有计算出的值保留在堆栈中，而只需在内存中保留4个变量即可。

这应该计算得更快，并使用更少的内存。