Sitemap
The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +772K followers.

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…

--

--

The Startup
The Startup

Published in The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +772K followers.

Andrew Pritchard
Andrew Pritchard

Written by Andrew Pritchard

The stories I write are a part of a learning journey through life, logic and programming. Share this journey with me.

No responses yet