使用线性递归计算第 n 个斐波那契数

Question

我已经尝试二进制递归找到第n个斐波那契数（或通过在main()中使用for循环找到整个斐波那契数列）但是根据Data Structures and Algorithms in Java（第 6 版）作者：Michael T. Goodrich；这是一种非常低效的方法，因为它需要对该方法进行指数级调用。一种有效的递归技术是线性递归，如下所示；

/**Returns array containing the pair of Fibonacci numbers, F(n) and F(n-1)*/
public static long[] fibonacciGood(int n) {
    if(n<=1) {
        long[] answer = {n,0};
        return answer;
    }else {
        long[] temp = fibonacciGood(n-1);               //returns {F(n-1), F(n-2)
        long[] answer = {temp[0]+temp[1], temp[0]};     //we want {F(n), F(n-1)}
        return answer;
    }
}

每当我运行代码它 returns 作为参考 [J@15db9742

这不是您想要的答案。我应该在 main() 中写些什么才能得到想要的答案？

Answer 1

您正在尝试将数组打印到控制台，这导致输出数组的内存地址。您可能想要遍历返回的数组，打印每个元素以获得所需的输出。

Answer 2

试试下面这个。您可以参考 api here.

    public static void main(String[] args) {
        System.out.println(Arrays.toString(fibonacciGood(4)));
    }

Answer 3

这里是打印数组对象，所以你得到了这些结果。在内部它调用对象的 toString 方法，return getClass().getName() + "@" + Integer.toHexString(hashCode());。所以你得到的价值是 [J@15db9742.

您可以直接使用 convert ，如下所示（适用于 Java 版本 5 及更高版本）

System.out.println(Arrays.toString(fibonacciGood(4)));

您可以通过将其转换为如下列表来打印它（在 Java 8 或更高版本中）（此处不宜使用流，但仅供参考） :

System.out.println(Arrays.stream(fibonacciGood(4)).boxed().collect(Collectors.toList()));

使用线性递归计算第 n 个斐波那契数

Computing the nth Fibonacci number using linear recursion

java

recursion

fibonacci

coding-efficiency