java - 使用 BigIntegers 和 memoization 调用递归方法时获取 NULL

Question

我使用长数据类型使该方法正常工作，但是当我去调用 BigInteger 递归方法时，当我 println 时它显示“null”。 这是我适用的长递归方法:

public static long fib_rec(int n){
    long result=1;
    if(n<=2){
        return result;
    }
    else{
        if(fval[n]!=0){
            result=fval[n];
        }
        else{
            result = fib_rec(n-1) + fib_rec(n-2);
            fval[n] = result;
        }
        return result;
    }
}

同样，该方法工作得很好，直到我超过 n = 94，此时值对于长数据类型来说太大了。 这是我的 BigInteger 尝试，完整的程序:

public class BigInt {

    static BigInteger[] fval;

    public static void main(String[] args) {

        int index;

        Scanner input = new Scanner(System.in);

        index = input.nextInt();

        fval = new BigInteger[index + 1];


        System.out.println(fib_rec(index));
    }

    public static BigInteger fib_rec(int index){

        BigInteger result = BigInteger.ONE;

        if(index <= 2){
            return result;
        }

        else{
            if(fval[index] != BigInteger.ZERO){
                result=fval[index];
            }
            else{
                 result = fib_rec(index-1).add(fib_rec(index-2));

                fval[index] = result;

            }
            return result;
        }
    }  
  }

这返回 null，我不知道为什么......

Answer 1

您假设 BigInteger 数组像长数组一样开始填充零，但它开始填充空值，因为它是一个对象数组，所以这样:

if(fval[index] != BigInteger.ZERO){
    result=fval[index];
}

将始终返回 null，因为 null 值不等于 BigInteger.ZERO。

如果添加此内容:

for (int i = 0; i < index+1; i++) {
  fval[i] = BigInteger.ZERO;
}

在调用 fib_rec 之前，它就可以工作了。