使用线性递归计算第n个斐波那契数 [英] Computing the nth Fibonacci number using linear recursion

问题描述

我尝试了二进制递归来找到第n个斐波那契数(或通过使用main()中的for循环来查找整个斐波那契数列)，但是根据中的数据结构和算法Java (第6版)，作者:Michael T. Goodrich；这是一种效率极低的方法，因为它需要对该方法进行指数级的调用.一种有效的递归技术是线性递归，如下所示；

I have tried binary recursion to find the nth Fibonacci number (or the whole Fibonacci series by using a for loop in main()) but according to Data Structures and Algorithms in Java (6th Edition) by Michael T. Goodrich; it is a terribly inefficient method as it requires an exponential number of calls to the method. An efficient recursion technique is linear recursion given as follows;

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

每当我运行代码时，它都会返回一个引用为 [ J @ 15db9742

Whenever I run the code it returns a reference as [J@15db9742

这不是所需的答案.我应该在main()中写些什么，以便得到想要的答案?

which is not the desired answer. What should I write in main() so that i can have the desired answer?

推荐答案

尝试以下方法.您可以引用api 这里.

Try the one below. You can refer the api here.

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

这篇关于使用线性递归计算第n个斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！