# The Fibonacci Sequence

### The Fibonacci Sequence

The fibonacci sequence is a sequence of numbers that can be defined
recursively. The first 10 numbers of the fibonacci sequences are:
0,1,1,2,3,5,8,13,21,34. You can calculate any given fibonacci number,
`n`

, by adding up the two previous fibonacci numbers.

Write a function that will compute the nth fibonacci number for any given
number, n. You can test your implementation in `ghci`

and compare it to the
example:

```
λ fibonacci 0
0
λ fibonacci 1
1
λ fibonacci 5
5
λ fibonacci 10
55
λ fibonacci 25
75025
```

### Hints

## Click to reveal

There are *two* cases where the example `fibonacci`

function isn’t recursive:

- The 0th fibonacci number is 0
- The 1st fibonacci number is 1

## Click to reveal

The recursive case of `fibonacci`

needs to make *two* recursive calls, because
it needs to add the next *two* smallest fibonacci values.

### Solution

## Click to reveal

You can implement the `fibonacci`

function using either `if`

expressions or
guards. We’ll use guards in this solution.

The definition of `fibonacci`

is similar to the `factorial`

that you should have
created in the previous exercise. Let’s take a look:

```
fibonacci n| n <= 0 = 0
| n == 1 = 1
| otherwise = fibonacci (n - 1) + fibonacci (n - 2)
```

Once again, you’ll notice that we’re being a bit generous with our smallest base
case. We’re checking for numbers *less than or equal to* zero so that we can
give a sensible answer even if the user passes in a negative number.

In the next base case, we check to see if our value is `1`

. If so, we just
return `1`

. These two base cases let use get the sequence started with the first
two numbers:

```
0 = 0
fibonacci 1 = 1 fibonacci
```

In the next step, `n`

is `2`

. This is a recursive case, and we’re going to look
back both one step to `n = 1`

and two steps to `n = 0`

:

```
2 = fibonacci (2 - 1) + fibonacci (2 - 2)
fibonacci = fibonacci 1 + fibonacci 0
= 1 + 1
= 1
```

Let’s follow up one more time, just to make sure we have the pattern down.

```
3 = fibonacci (3 - 1) + fibonacci (3 - 2)
fibonacci = fibonacci 2 + fibonacci 1
= (fibonacci (2 - 1) + fibonacci (2 - 2)) + 1
= (fibonacci 1 + fibonacci 0) + 1
= (1 + 0) + 1
= 1 + 1
= 2
```

Remember, when you’re working with recursive functions, try to walk through the recursion manually if you’re having trouble understanding how the function works.