在 Java 中使用 BigInteger 的递归斐波那契数列

Question

我正在尝试解决 java 中的项目 euler 25 问题，因为我需要一些东西来存储 10000 位数字，所以我正在使用 BigInteger 类。

所以我正在使用 BigIntegers 处理一些递归斐波那契数列，我正在尝试转换此代码：

public int fibonacci(int n)  {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

来自这个link：Java recursive Fibonacci sequence

相同的代码，但使用 BigIntegers。

所以，这就是我目前所拥有的：

public static BigInteger fibonacci(BigInteger index) {
    if (index.compareTo(BigInteger.ZERO) == 0)
        return BigInteger.ZERO;
    else if (index.compareTo(BigInteger.valueOf(1)) == 1)
        return BigInteger.ONE;
    else
        return fibonacci(index.subtract(BigInteger.ONE)).add(fibonacci(index.subtract(BigInteger.valueOf(2))));
}

public static int numberOfDigits(BigInteger fibonacci) {
    return Integer.valueOf(fibonacci.toString().length());
}

public static void main(String[] args) {
    long startTime = System.nanoTime();
    for (BigInteger i = new BigInteger("1"); numberOfDigits(fibonacci(i)) <= 1000; i = i.add(BigInteger.ONE))
        System.out.println(" " + i + "  -  " + fibonacci(i) + "  -  " + numberOfDigits(fibonacci(i)));
    long endTime = System.nanoTime();
    long duration = (endTime - startTime);
    System.out.println("Duration: " + duration/1000000 + " ms");
}

当我运行它时，我得到一个 WhosebugError，像这样：

Exception in thread "main" java.lang.WhosebugError
    at java.math.BigInteger.subtract(BigInteger.java:1423)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)

它重复了 1000 次。好吧，我不知道出了什么问题，所以请你们能帮帮我吗？谢谢！

Answer 1

我认为你有递归的标准问题......这是斐波那契方法的问题，因为你没有地方，当这个方法必须 return 最终结果时，所以请检查你的条件和更多关于比较在大整数中。推荐阅读尾递归

Answer 2

当您使用 compare() 时 returns 1 如果参数高于实际值。

所以你应该修改这段代码：

else if (index.compareTo(BigInteger.valueOf(1)) == 1)

为此：

else if (index.compareTo(BigInteger.valueOf(1)) == 0)

Answer 3

Java 不能很好地处理深度递归。您应该改为使用循环。

另见关于尾递归的帖子：https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all

Answer 4

您可以尝试使用动态规划来降低 space 复杂性。这样的事情应该有效：

public static BigInteger fibonacci(BigInteger n) {
    if (n.compareTo(BigInteger.valueOf(3L)) < 0) {
        return BigInteger.ONE;
    }
    //Map to store the previous results
    Map<BigInteger, BigInteger> computedValues = new HashMap<BigInteger, BigInteger>();
    //The two edge cases
    computedValues.put(BigInteger.ONE, BigInteger.ONE);
    computedValues.put(BigInteger.valueOf(2L), BigInteger.ONE);
    return fibonacci(n, computedValues);
}

private static BigInteger fibonacci(BigInteger n, Map<BigInteger, BigInteger> computedValues) {
    if (computedValues.containsKey(n))
        return computedValues.get(n);
    BigInteger n1 = n.subtract(BigInteger.ONE);
    BigInteger n2 = n.subtract(BigInteger.ONE).subtract(BigInteger.ONE);
    computedValues.put(n1, fibonacci(n1, computedValues));
    computedValues.put(n2, fibonacci(n2, computedValues));
    BigInteger newValue = computedValues.get(n1).add(computedValues.get(n2));
    computedValues.put(n, newValue);
    return newValue;
}

在 Java 中使用 BigInteger 的递归斐波那契数列

Recursive Fibonacci using BigInteger in Java

java

fibonacci