# On memoization

Published in

--

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 stories I write are a part of a learning journey through life, logic and programming. Share this journey with me.