Slow and Fast Fibonacci

Fibonacci.swift

//: Playground - noun: a place where people can play

import Foundation
import UIKit

func fib(_ n: Int) -> Int {
    if n == 0 { return 0 }
    if n == 1 { return 1 }
    return fib(n - 1) + fib(n - 2)
}

// Cache the previously computed fib(n) value
func fibMemoed(_ n: Int, memo: inout [Int: Int]) -> Int {
    if n == 0 { return 0 }
    if n == 1 { return 1 }
    
    if memo[n] == nil {
        memo[n] = fibMemoed(n - 1, memo: &memo) + fibMemoed(n - 2, memo: &memo)
    }
    
    return memo[n]!
}

// Measuers, roughly the time it took for a block of "work" to complete
func measure(work: () -> Void) -> CFTimeInterval {
    let startTime = CACurrentMediaTime()
    work()
    let endTime = CACurrentMediaTime()
    return endTime - startTime
}

// -------------
let n = 21

// Sould be fast
measure {
    var memo = [Int: Int]()
    let _ = fibMemoed(n, memo: &memo)
}

// Should be slow(er)
measure {
    let _ = fib(n)
}