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
}