java - 斐波那契递归不适用于 Java

Question

请原谅我的无知，我还是个菜鸟。每当我输入一个中等大的数字时，它不会给我任何输出，因为它卡在 fibCalculate 方法中。不提供任何输出的数字示例是 40。

package fib;

import java.math.BigInteger;
import java.util.Scanner;


public class FibonacciCalculator {
    private static BigInteger TWO = BigInteger.valueOf(2);

    public static BigInteger fibCalculate(BigInteger num) {
        if (num.equals(BigInteger.ONE) || num.equals(BigInteger.ZERO)) {
            return num;
        } else {
            return (fibCalculate(num.subtract(BigInteger.ONE)).add(fibCalculate(num.subtract(TWO))));
        }
    }

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner input = new Scanner(System.in);
        long n = 10;

        System.out.println(
                "Please input a fibonacci placeholder to see what fibonacci number it holds,\nor input 0 to end program. (The count starts at 0):  ");
        n = input.nextLong();
        System.out.println("Answer: "+fibCalculate(BigInteger.valueOf(n)));

    }
}

Answer 1

您的代码确实会产生 n>40 的输出，只是需要很多时间，因为它非常慢。

例如，使用以下代码测试您的代码是否包含 0 到 50 之间的所有 n 值:

long start = System.currentTimeMillis ();
for (int fib=0;fib<50;fib++) {
  System.out.println("Answer: "+ fib + ": "+fibCalculate(BigInteger.valueOf(fib)) + " after " + (System.currentTimeMillis ()-start)/1000 + " seconds from the beginning");
}

产生以下输出(我没有等待它结束):

Answer: 0: 0 after 0 seconds from the beginning
Answer: 1: 1 after 0 seconds from the beginning
Answer: 2: 1 after 0 seconds from the beginning
Answer: 3: 2 after 0 seconds from the beginning
Answer: 4: 3 after 0 seconds from the beginning
Answer: 5: 5 after 0 seconds from the beginning
Answer: 6: 8 after 0 seconds from the beginning
Answer: 7: 13 after 0 seconds from the beginning
Answer: 8: 21 after 0 seconds from the beginning
Answer: 9: 34 after 0 seconds from the beginning
Answer: 10: 55 after 0 seconds from the beginning
Answer: 11: 89 after 0 seconds from the beginning
Answer: 12: 144 after 0 seconds from the beginning
Answer: 13: 233 after 0 seconds from the beginning
Answer: 14: 377 after 0 seconds from the beginning
Answer: 15: 610 after 0 seconds from the beginning
Answer: 16: 987 after 0 seconds from the beginning
Answer: 17: 1597 after 0 seconds from the beginning
Answer: 18: 2584 after 0 seconds from the beginning
Answer: 19: 4181 after 0 seconds from the beginning
Answer: 20: 6765 after 0 seconds from the beginning
Answer: 21: 10946 after 0 seconds from the beginning
Answer: 22: 17711 after 0 seconds from the beginning
Answer: 23: 28657 after 0 seconds from the beginning
Answer: 24: 46368 after 0 seconds from the beginning
Answer: 25: 75025 after 0 seconds from the beginning
Answer: 26: 121393 after 0 seconds from the beginning
Answer: 27: 196418 after 0 seconds from the beginning
Answer: 28: 317811 after 0 seconds from the beginning
Answer: 29: 514229 after 0 seconds from the beginning
Answer: 30: 832040 after 0 seconds from the beginning
Answer: 31: 1346269 after 0 seconds from the beginning
Answer: 32: 2178309 after 0 seconds from the beginning
Answer: 33: 3524578 after 1 seconds from the beginning
Answer: 34: 5702887 after 1 seconds from the beginning
Answer: 35: 9227465 after 2 seconds from the beginning
Answer: 36: 14930352 after 4 seconds from the beginning
Answer: 37: 24157817 after 6 seconds from the beginning
Answer: 38: 39088169 after 10 seconds from the beginning
Answer: 39: 63245986 after 17 seconds from the beginning
Answer: 40: 102334155 after 28 seconds from the beginning
Answer: 41: 165580141 after 45 seconds from the beginning
Answer: 42: 267914296 after 74 seconds from the beginning
Answer: 43: 433494437 after 120 seconds from the beginning

您可以看到运行时间呈指数增长。