0

I am learning Java and I have this code from the internet and running it in Eclipse: 

public class Fibonacci {

    public static void main (String [] args) { 
        for (int counter = 0; counter <= 3; counter++){
            System.out.printf("Fibonacci of %d is: %d\n",  counter, fibonacci(counter));

    }

    public static long fibonacci(long number) {
        if ((number == 0) || (number == 1))
             return number;
        else
             return fibonacci(number - 1) + fibonacci(number - 2);
    }
}

I've tried to understand it but cannot get it. So I run through the code and counter gets passed in through the fibonacci method. As counter starts at 0 and this is what gets passed first, then 1 and I understand the method passes back 0 and then 1.

When it reaches 2: it will return 2-1 + 2-2 = 2 and it does return this.
When it reaches 3: it will return 3-1 + 3-2 = 3 but it does not return 3 it returns 2.

Please can someone explain to me why as I cannot figure this out?

Thanks

gkrls
  • 2,618
  • 2
  • 15
  • 29
John
  • 15
  • 3
  • 1
    [possible dup](http://stackoverflow.com/q/8965006/2587435) - Also you may want to do some research on "recursion" – Paul Samsotha Aug 16 '14 at 13:54
  • use 3 `println`s in the `fibonacci` function to display: (1) when it is called, with the parameter value; (2) & (3) on each path through the function just before the `return`. Then look at the results and you should be able to understand it. [or use a debugger] – TooTone Aug 16 '14 at 13:56
  • 1
    fib(2)=fib(2-1)+fib(2-2)=fib(1)+fib(0)=1+0=1. fib(3)=fib(3-1)+fib(3-2)=fib(2)+fib(1)=1+1=2. – Eran Aug 16 '14 at 13:57
  • Also, be careful when you evaluate arithmetic expressions by hand. `2-1 + 2-2`= `1 + 0`. – laune Aug 16 '14 at 14:18
  • @Eran thanks that helped but only after reading the below and working out what was going on, but this makes alot of sense now: (3)=fib(3-1)+fib(3-2)=fib(2)+fib(1)=1+1=2. So it calls the methods as (3-1) + 3-2) = fib(2) + fib(1) = 1+1 = 2. – John Aug 16 '14 at 14:52

1 Answers1

0

First, I have to tell you that this recursive version has a dramatic exponential cost. Once you understand how it works, my advice for you would be to learn about tail recursivity, write a tail-recursive solution, an iterative solution, and compare them to your current method for high values of "number".

Then, your function basically uses the mathematical definition of the Fibonacci sequence :

f0 = 1, f1 = 1, fn = fn-1 + fn-2 for all n >= 2

For example if we call fibonacci(3), this will return fibonacci(2) + fibonacci(1). fibonacci(2) will be executed first and will return fibonacci(1) + fibonnacci(0). Then fibonacci(1) will return immediately 1 since it is a terminal case. It happens the same thing with fibonnacci(0), so now we have computed fibonnacci(2) = 1 + 0 = 1. Let's go back to fibonacci(3) which has been partially evaluated at this point : 1 + fibonnacci(1). We just have to compute fibonnacci(1) and we can finally return 1 + 1 = 2.

Even in this little example, you can see that we evaluated twice fibonacci(1), that is why this version is so slow, it computes many times the same values of the sequence, and it gets worth when "number" is high.

Dici
  • 25,226
  • 7
  • 41
  • 82
  • I understood from your example and reading others, so you put in fibonacci(3) this will return fibonacci(2) + fibonacci(1). Which returns fibonacci(1) + fibonacci(0). Then works forward and gives these values to fibonacci(3). But confused at the part where you have written: so now we have computed fibonnacci(2) = 1 + 1 = 2. As fibonacci(2) was = 1 as fibonacci(1) + fibonacci(0) is 1. And the part where you wrote We just have to compute fibonnacci(1) and we can finally return 2 + 1 = 3. But it didnt return 3 for fibonacci(3) it returned 2. – John Aug 16 '14 at 14:38
  • My bad, I used another definition of the fibonacci sequence where f0 = 1, f1 = 1 and so on whereas you define with f0 = 0, f1 = 1 so the result I gave you was not f3 with your definition but f2. I correct it. Now as I told you I strongly recommend you to read about tail-recursivity and also to try to write an iterative version. You will see how recursivity can provide poor performances if not well used. – Dici Aug 16 '14 at 14:54