JavaでBigIntegerを使用する再帰的なフィボナッチ

Question

私は10000桁の数値を格納するために何か必要なので、プロジェクトのユーラー問題を解決しようとしています。私はBigIntegerクラスを使用しています。

だから私はのBigIntegerを使用して、いくつかの再帰的フィボナッチ数列に働いていると私は、このコードを変換しようとしている：

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

このリンクから：Java recursive Fibonacci sequence

同じコードに、しかしのBigIntegerを使用して。

だから、これは私がこれまで持っているものです。

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"); 
} 

私はそれを実行すると、私はこのように、StackOverFlowErrorを得る：

Exception in thread "main" java.lang.StackOverflowError 
    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

compare()を使用すると、引数が実際よりも高い場合は1が返されます。このため

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

：

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

Answer 2

私は再帰に関する標準的な問題があると思います...フィブリノッチのメソッドには問題があります。このメソッドは最終結果を返さなければならないので、BigIntegerで条件を確認してください。テール再帰についてもお勧めします

Answer 3

Javaが深い再帰とあまりにもよく扱わない

だからあなたは、コードのこの部分を変更する必要があります。代わりにループを使用して変換する必要があります。あなたは宇宙の複雑さを軽減するために、動的プログラミングを使用しようとすることができhttps://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all

Answer 4

：

はまた、末尾再帰でこのスレッドを参照してください。このようなものはうまくいくはずです：

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; 
}