Fibonacci Sequence Algorithms Revisited

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!