The algorithm for returning the \(nth \) number in the Fibonacci Sequence provides a simple demonstration on how different design choices effect the run time, storage, and readability of the code.

The sequence is as follows:

`1, 1, 2, 3, 5, 8, 13, 21, 34, 55`

The sequence follows the pattern of:

\(fib(n) = fib(n – 1) + fib(n – 2)\) where \(n > 0 \)I’ve written three algorithms. Each has pros and cons.

First I want to create a simple Error for a case where \(n\) is out of bounds. We will use this with all our algorithms.

```
enum FibError: Error {
case OutOfBounds
}
```

Our first algorithm will use an iterative approach.

```
func fib(of n: Int) throws -> Int {
guard n > 0 else { throw FibError.OutOfBounds }
guard n > 2 else { return 1 }
var result = 0, nMinusOne = 1, nMinusTwo = 1
for _ in 3...n {
result = (nMinusOne + nMinusTwo)
nMinusTwo = nMinusOne
nMinusOne = result
}
return result
}
```

Our second algorithm will use a recursive approach. Notice how this algorithm is easier to read, but slightly more difficult to conceive.

```
func fib(of n: Int) throws -> Int {
guard n > 0 else { throw FibError.OutOfBounds }
guard n > 2 else { return 1 }
return try fib(of: n - 1) + fib(of: n - 2)
}
```

Our third algorithm is a more optimal version of the recursive algorithm. Because of the nature of the recursive function calls, and more specifically the operation` try fib(of: n - 1) + fib(of: n - 2)`

, we use a dictionary to avoid repetitive function calls.

```
var sequenceValues = [Int: Int]()
func fib(of n: Int) throws -> Int {
guard n > 0 else { throw FibError.OutOfBounds }
guard n > 2 else { return 1 }
var value: Int
if sequenceValues[n] != nil {
value = sequenceValues[n]!
} else {
value = try fib(of: n - 1) + fib(of: n - 2)
sequenceValues[n] = value
}
return value
}
```

I hope this was helpful!