Fibonacci

//Slow Implementation
func fib1(x: Int) -> Int {
    return x < 2 ? x : fib1(x - 1) + fib1(x - 2)
}

let m = fib1(5)


//Fib Trivial Memoization
var memoizeDict = Dictionary<Int, Double>()

func fib2(x: Int) -> Double {
    
    if let value = memoizeDict[x] {
        return value
    }
    
    if x < 2 {
        return Double(x)
    }
    else {
        memoizeDict[x] = fib2(x - 1) + fib2(x - 2)
        return memoizeDict[x]!
    }
}

let x = fib2(5)



////Fib Faster Memoization
func memoize<T: Hashable, U>(body: ((T) -> U, T) -> U) -> (T) -> U {
    var memo = Dictionary<T, U>()
    var result: ((T) -> U)!
    result = {
        x in
        if let q = memo[x] { return q }
        let r = body(result, x)
        memo[x] = r
        return r
    }
    return result
}

//var fib3: (Int) -> Int = { $0 }
let fib3 = memoize {
    fib3, x in
    x < 2 ? x : fib3(x - 1) + fib3(x - 2 )
}

let y = fib3(5)