On memoization

Andrew Pritchard
Jun 17, 2019 · 6 min read

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: