fibonacci.swift

// recursively with redundant calculations
func fibo(n: Int) -> Int {
    if n < 2 { return n }
    return fibo(n: n - 1) + fibo(n: n - 2)
}

// with memoization
var memo = Dictionary<Int, Int>()

func fibMemo(_ n: Int) -> Int {
    if let result = memo[n] { return result }
    if n < 2 { return n }
    
    let result = fibMemo(n - 1) + fibMemo(n - 2)
    memo[n] = result
    return result
}

let results = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
for i in 0...11 {
    assert(fibMemo(i) == results[i])
}