Computing the nth Fibonacci number using linear recursion

Question

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

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

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

Unrelated but since you are interested in efficiency here: also note that there is a simple closed form solution to any Fibonacci type sequence which doesn't require any loops or recursion at all. — user268396, Oct 11 '19 at 17:28
Please read the duplicate really carefully. You do not have a problem with recursion. Your problem is that you do not understand what System.out.println(someArray) does.If you look at the answer which you accepted here, and the accepted answer on the DUP question ... guess what: they say the same. — GhostCat, Oct 11 '19 at 18:00
@EqraKhattak: [Wikipedia covers this](https://en.wikipedia.org/wiki/Fibonacci_number#Generalizations) take a look at the section titled "Closed-form expression" — user268396, Oct 11 '19 at 18:08
@GhostCat Sadly actually, I don't understand how this recursion method is called in main(). I don't know how it matters if the answer is same for a question on array. The context is totally different. — eqrakhattak, Oct 11 '19 at 18:09

score 1 · Accepted Answer · answered Oct 11 '19 at 17:17

1

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

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

answered Oct 11 '19 at 17:17

Subramanian Mariappan

3,736
1
14
29

That worked well for me. thanks alot! – eqrakhattak Oct 11 '19 at 17:42

score 0 · Answer 2 · answered Oct 11 '19 at 17:16

0

You are trying to print out an array to the console, this is causing the memory address of the array to be output. You may want to iterate through the array returned, printing every element to get the desired output.

answered Oct 11 '19 at 17:16

Steven

41
3

It is not really the memory address though. – GhostCat Oct 11 '19 at 17:29
@GhostCat what reference is that? – eqrakhattak Oct 11 '19 at 17:46

Gaurav Jeswani · Answer 3 · 2019-10-11T17:38:27.393

-1

Here you are printing the array object, so you are getting these results. Internally it calls toString method of the object, which return getClass().getName() + "@" + Integer.toHexString(hashCode());. So you are getting value as [J@15db9742.

You can use convert is directly as below (Working in Java version 5 and above)

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

You can print it by converting it to list as below (in Java 8 or above) (Not Preferable to use streams here, but just for knowledge):

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

edited Oct 11 '19 at 17:38

answered Oct 11 '19 at 17:19

Gaurav Jeswani

4,410
6
26
47

The first option is like super overkill. Thats like carving the numbers into granite plates, to then ship them around the globe, to then have a person read them to you on the phone ... – GhostCat Oct 11 '19 at 17:29
thanks a lot but I didn't understand your (java 8 or above) code. Can you pls explain it. – eqrakhattak Oct 11 '19 at 17:34
Please do not suggest the excessive and unnecessary use of streams. – Leviathan Oct 11 '19 at 17:34
@GhostCat you marked my Question as duplicate, i can't see why. The question u marked me duplicate to, is totally about **array** but I'm talking about **recursion** here. – eqrakhattak Oct 11 '19 at 17:37
@GhostCat : Thanks to mention that. But I just placed it for knowledge purpose as Eqra looks like new to Java. But I have updated as NOTE to not use that approach. – Gaurav Jeswani Oct 11 '19 at 17:40
@Eqra Khattak : Here in Java 8 approach we are converting it to List using Stream. Which was added in Java 8. And as toString() method in List is overridden method, it will print the data. As array is of type primitive and List can be created of primitive, so we are casting it to Boxed Primitive long to Long. – Gaurav Jeswani Oct 11 '19 at 17:44
@GauravJeswani I see. – eqrakhattak Oct 11 '19 at 17:50
@EqraKhattak And I cant see why you claim "they are different", when the answer you accepted, and the answer that is accepted on the DUP ... do the exact same thing. – GhostCat Oct 11 '19 at 18:00

Computing the nth Fibonacci number using linear recursion

3 Answers3

Linked