## Recursion: Fibonacci Numbers

Check out the resources on the page's right side to learn more about recursion. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book Cracking the Coding Interview.

*The Fibonacci Sequence*

The Fibonacci sequence begins with and 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 :

**Task**

Given , complete the *fibonacci* function so it returns .

**Input Format**

Locked stub code in the editor reads a single integer denoting the value of and passes it to the *fibonacci* function.

**Constraints**

**Output Format**

Locked stub code in the editor prints the value of returned by the *fibonacci* function.

**Sample Input**

```
3
```

**Sample Output**

```
2
```

**Explanation**

Consider the Fibonacci sequence:

...

We want to know the value of . If we look at the sequence above, evaluates to . Thus, we print as our answer.