Need to explain with Fibonacci

Question

I have seen many examples of Fibonacci here on Stack Overflow but I have found no answer for my question. So, I have a code:

public class Fib {
    public static int fib(int n) {
        if (n < 2) {
           return n;
        }
        else {
   return fib(n-1)+fib(n-2);
        }
}

public static void main(String[] args) {
    for (int i=0; i<8; i++)
        System.out.print(fib(i)+", ");
}
}

After run it we will get 0, 1, 1, 2, 3, 5, 8, 13,

I have a question: How do we get 8 ? fib(6)=............

Can anyone write in detail?

Trace out what happens if you run `fib(6)` yourself on a piece of paper and you can see what is going to happen. — Leigh, Apr 06 '14 at 13:42
possible duplicate of [Java recursive Fibonacci sequence](http://stackoverflow.com/questions/8965006/java-recursive-fibonacci-sequence). This question already pretty explained, here — SBotirov, Apr 06 '14 at 13:50
Should be closed as doesn't show a minimum understanding of the problem (just glance at comments on answers). — OJFord, Apr 06 '14 at 14:16

score 1 · Answer 1 · answered Apr 06 '14 at 13:44

1

fib(0) = 0
fib(1) = 1
fib(2) = fib(1) + fib(0) = 1
fib(3) = fib(2) + fib(1) = 2
fib(4) = fib(3) + fib(2) = 3
fib(5) = fib(4) + fib(3) = 5
fib(6) = fib(5) + fib(4) = 8

When you call fib(6) it will execute fib(5) and fib(4) etc. until it hits the base cases fib(1) and fib(0).

answered Apr 06 '14 at 13:44

Thorkil Holm-Jacobsen

7,287
5
30
43

Can you write more detail this fib(6) = fib(5) + fib(4) = .........................................................=8 – Vit Rasmussen Apr 06 '14 at 13:47
@Sven.. all other details in same answer. Now yourself try it out to find out for other :) – Pradeep Simha Apr 06 '14 at 13:49
@Sven Start with `fib(6)=fib(5)+fib(4)` and substitute `fib(5)` and `fib(4)`, and keep on substituting until you're only left with constants. Here's the first step: `fib(6)=fib(5)+fib(4)=fib(4)+2*fib(3)+fib(2)=...` – VH-NZZ Apr 06 '14 at 13:52
I mean like this fib(3) = fib(2) + fib(1) //so we we are into the else statement, because 3 > 1 = fib(2) + 1 //fib(1) = 1 because 1 <= 1 so you return it (if statement) = (fib(1) + fib(0)) + 1 //2 > 1 => we go to the else statement = (1 + 0) + 1 //0 <= 1 & 1 <= 1 so we are into the if and return the values = 2 – Vit Rasmussen Apr 06 '14 at 13:54
Just remember that `fib(n+1)=fib(n)+fib(n-1)`, with initial conditions `fib(1)=1, fib(0)=0`. Now you code this however you want but whenever you encounter either conditions above, you return the corresponding value. – VH-NZZ Apr 06 '14 at 13:57

score 0 · Answer 2 · answered Apr 06 '14 at 13:44

0

fib(6) = fib(5) + fib(4)  //..
fib(5) = fib(4) + fib(3)  //..
fib(4) = fib(3) + fib(2)  //2 + 1 
fib(3) = fib(2) + fib(1)  //1 + 1
fib(2) = fib(1) + fib(0)  //1 + 0  Begin here (stop condition)

answered Apr 06 '14 at 13:44

Maroun

94,125
30
188
241

Can you write more detail this fib(6) = fib(5) + fib(4) = .........................................................=8 – Vit Rasmussen Apr 06 '14 at 13:47
That's all details you need. Think. – Maroun Apr 06 '14 at 13:48
i mean like this fib(3) = fib(2) + fib(1)= fib(2) + 1 = (fib(1) + fib(0)) + 1 = (1 + 0) + 1 = 2 – Vit Rasmussen Apr 06 '14 at 13:55
Well.. it's exactly the same.. Just put some line into other. – Maroun Apr 06 '14 at 13:56

score 0 · Accepted Answer · answered Apr 06 '14 at 14:11

fib(6) = fib(5)+fib(4) = fib(4)+fib(3)+fib(3)+fib(2) = fib(3)+fib(2)+fib(2)+fib(1)+fib(2)+fib(1)+fib(1)+fib(0) = fib(2)+fib(1)+fib(1)+fib(0)+fib(1)+fib(0)+1+fib(1)+fib(0)+1+1+0 = fib(1)+fib(0)+1+1+0+1+0+1+1+0+1+1+0 = 1+0+1+1+0+1+0+1+1+0+1+1+0=8

Hope it helped..

Need to explain with Fibonacci

3 Answers3