Memoization caches completed computations so repeated requests for the same inputs return stored results instead of triggering recomputation. It addresses recursive Fibonacci’s repeated subproblems: the naive implementation expands exponentially and becomes impractical even for modest inputs. section 1.1
A Swift implementation develops the technique in small steps:
- Create a dictionary keyed by the function’s input and prefill known base cases. section 1.1
- Return a cached value immediately when the input is already present. section 1.1
- Otherwise compute the result recursively, store it, and return the stored value. section 1.1
- For Fibonacci, memoization reduces the calls for fib(20) from 21,891 to 39; an iterative solution can be even more performant. section 1.1
Where memoization helps
Memoization suits work whose results are likely to be requested again. Applications include parsers and language runtimes; some Prolog runtimes automatically memoize function calls. section 1.6
var fibMemo: [UInt: UInt] = [0: 0, 1: 1] // our old base cases
func fib3(n: UInt) -> UInt {
if let result = fibMemo[n] { // our new base case
return result
} else {
fibMemo[n] = fib3(n: n - 1) + fib3(n: n - 2) // memoization
}
return fibMemo[n]!
}
Inspect the complete Swift memoized Fibonacci function, including the dictionary, cached lookup, recursive cases, and stored result. section 1.1
