Member-only story
On memoization
Summary:
Using “open” recursion:
- We can separate memoization logic from function logic.
- We can memoize functions without modifying the syntax of the function.
- We can make functions generic across multiple types of memoization.
Memoization in Rust.
Consider a recursive function. The most basic example is the Fibonacci sequence. Here is a naive implementation:
fn fib_naive(arg: u32) -> u32 {
match arg {
0 => 0,
1 => 1,
n => fib_naive(n - 1) + fib_naive(n - 2),
}
}fn main() {
assert_eq!(fib_naive(40), 102334155);
}
Calculating fib_naive(40)
on my computer takes almost a second. If we look at this function, we can reason about it’s performance. The result of fib_naive
is going to be 0
, 1
or the result of two calls to fib_naive
added together. If we only have 0
, 1
, and addition at our disposal, then it will take at least fib_naive(n)
additions to calculate fib_naive(n)
. This is unacceptable performance for anything but the smallest values of n
.
Memoizing the results
One way to improve performance is to memoize the results. That means that when we call our function, we record what the result is in some kind…