The Fibonacci sequence begins with* Fibonacci(0) = 0* and *Fibonacci(1)=1* as its respective first and second terms. After these first two elements, each subsequent element is equal to the sum of the previous two elements.

Here is the basic information you need to calculate *Fibonacci(n)*:

- Fibonacci(0) = 0
- Fibonacci(1) = 1
- Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

**Task**

Given n, complete the *fibonacci* function so it returns Fibonacci(n).

**Input Format**

Nth number

**Output Format**

Fibonacci() Nth number.

**Sample Input**

1 2 |
3 |

**Sample Output**

1 2 |
2 |

**Explanation**

1 2 3 4 5 6 7 8 9 |
public static int Fibonacci(int n) { if (n == 0) return 0; else if (n == 1) return 1; else { return Fibonacci(n - 1) + Fibonacci(n - 2); } } |