java - 当 "n"的值较大时，递归函数运行时间过长

Question

我正在尝试获取 n 的值-th 系列。这样f(n)=2014*f(n-1) + 69*f(n-2)对于 (n>2)和f(n)=1对于 n<=2 。我正在使用BigInteger因为这是我的要求。在运行较小值的代码时，我得到了答案。当n超过例如 123 我没有得到结果。任何代码修改或缩短运行时间的方法？

public class test {
    public static BigInteger FindSumDigit (BigInteger number) {
         BigInteger one = new BigInteger("1");
         BigInteger two = new BigInteger("2");
         BigInteger result, zero = new BigInteger("0");
         BigInteger a = new BigInteger("2014");
         BigInteger b = new BigInteger("69");
         if(number.equals(one))
             return one;
         else if (number.equals(two))
             return one;
         else
             return a.multiply(FindSumDigit(number.subtract(one))).add(b.multiply(FindSumDigit(number.subtract(two)))); //finding the n-th element

    }

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        BigInteger q[] = new BigInteger[N];
        if(1 <= N && N < 10)
            for(int i = 0; i < N; i++) {
                BigInteger n = s.nextBigInteger();
                BigInteger o = FindSumDigit(n);
                System.out.println(o);
            }
     }
}

Answer 1

下面的递归函数是线性递归或“斐波那契式序列”的示例。

f(n)=2014*f(n-1) + 69*f(n-2) for (n>2)

虽然这个函数自然是递归定义的，但将此数学定义直接转换为程序是不使用递归的典型示例。事实上，计算机需要对给定输入 n 进行的函数调用次数本身就是斐波那契数列!由于第 n 个斐波那契数大约为 ((1 + sqrt(5))/2 )^n，因此函数调用的数量呈指数增长。对于较小的 n 值，这并不重要。但在某一点之后，计算机将要么锁定，要么抛出 StackOverflow 异常。

这是避免此问题的非递归解决方案:

static BigInteger a = new BigInteger("2014");
static BigInteger b = new BigInteger("69");   

public static BigInteger computeNthTerm(int n) {
   BigInteger prev1 = new BigInteger("1");
   BigInteger prev2 = new BigInteger("1");
   BigInteger nth = new BigInteger("1");
   for(int k=2; k<n; k++) {
      nth = prev2.multiply(a).add( prev1.multiply(b) );
      prev1 = prev2;
      prev2 = nth;
   }
   return nth;
}