Please explain this simple code:

public int fibonacci(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); }

I’m confused with the last line especially because if n = 5 for example, then fibonacci(4) + fibonacci(3) would be called and so on but I don’t understand how this algorithm calculates the value at index 5 by this method. Please explain with a lot of detail!

## Advertisement

## Answer

In fibonacci sequence each item is the sum of the previous two. So, you wrote a recursive algorithm.

So,

fibonacci(5) = fibonacci(4) + fibonacci(3) fibonacci(3) = fibonacci(2) + fibonacci(1) fibonacci(4) = fibonacci(3) + fibonacci(2) fibonacci(2) = fibonacci(1) + fibonacci(0)

Now you already know `fibonacci(1)==1 and fibonacci(0) == 0`

. So, you can subsequently calculate the other values.

Now,

fibonacci(2) = 1+0 = 1 fibonacci(3) = 1+1 = 2 fibonacci(4) = 2+1 = 3 fibonacci(5) = 3+2 = 5

And from fibonacci sequence `0,1,1,2,3,5,8,13,21....`

we can see that for `5th element`

the fibonacci sequence returns `5`

.

See here for Recursion Tutorial.