# Thread: recursion example using fibonacci

1. Member Join Date
May 2014
Posts
56
Rep Power
0

## recursion example using fibonacci

I'm having some difficulty understanding recursion. Example is below:

Java Code:
```public class Fibonacci {

private int fibonacci(int n){
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

private void test(){

for(int i=0;i<=4; i++){
System.out.println(i + " : " + fibonacci(i));
}

}

public static void main(String[] args) {
Fibonacci test = new Fibonacci();
test.test();

}

// output
0 : 0
1 : 1
2 : 1
3 : 2
4 : 3
}```
when i is 4, I don't understand how it produces 3. In my head, it should be producing 1. When fibonacci is called with 4, fibonacci(4 - 1) runs, which calls fibonacci(3), fibonacci(3-1) runs, which calls fibonacci(2), fibonacci(2-1) runs, which calls fibonacci(1), which returns value of 1. In other words, fibonacci(4 - 1) returns 1. Then we evaluate fibonacci(4 - 2), which calls fibonacci(2), fibonacci(2-2) runs, which calls fibonacci(0), which returns 0. So fibonacci(4-2) returns 0. Thus, 1-0=1. Yet the program returns 3. What am I missing about recursion?  Reply With Quote

2. Senior Member Join Date
Mar 2011
Posts
103
Rep Power
0

## Re: recursion example using fibonacci

You are missing some calls. There are potentially two recursive calls at each step. For example, when fibonacci(3) runs, it calls fibonacci(3-1) + fibonacci(3-2).  Reply With Quote

3. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
13

## Re: recursion example using fibonacci Originally Posted by johnmerlino which calls fibonacci(1), which returns value of 1. In other words, fibonacci(4 - 1) returns 1.
Well, it leads to 1 returning eventually, but remember that there are other calls in the call stack that also need returning. So fibonacci (4-1) is
really fibonacci(3) which ultimately returns 2. Fibonacci(4-2) is really fibonacci(2) which ultimately returns 1. 2 + 1 = 3.
So fibonacci (4) = 3.

Regards,
Jim  Reply With Quote

4. Member Join Date
May 2014
Posts
56
Rep Power
0

## Re: recursion example using fibonacci

ok makes sense now  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•