Dive C4.11.1 · part 1 of 3

Memoization & overlapping subproblems

Keep the recursion exactly as written, and hang a store off it. In F#, that store is a Dictionary or a Map.

Top-down dynamic programming is the smallest possible change to a recursion: before computing a subproblem, check a store; after, save the answer. Because the recursion is still driven by demand, it stays lazy — it only ever evaluates the subproblems the answer needs. The worked recurrence is fib n = fib (n-1) + fib (n-2). Without a store, a shared subproblem is re-derived along every path that reaches it, and the per-call counts are the Fibonacci numbers, so the work grows exponentially. With a store, each subproblem is evaluated once. F# gives two idiomatic stores — a mutable Dictionary and an immutable Map threaded through the recursion — and this dive uses both. Every // val it : echo below was produced by dotnet fsi.

Count the evaluations Module hub

C4.11.1 · part 1

The recursion that repeats itself

Written plainly, the Fibonacci recursion is honest about the recurrence and wasteful about the work. To compute fib 5 it computes fib 4 and fib 3; to compute fib 4 it computes fib 3 again, and so on. The same subproblem is solved on every branch that needs it, and the number of calls grows like the Fibonacci numbers themselves.

// plain recursion — every shared subproblem re-derived per branch
let rec fib n =
    if n < 2 then n
    else fib (n - 1) + fib (n - 2)
// val fib: n: int -> int

fib 10   // val it: int = 55  — but 177 calls to get there

The answer is right; the cost is the problem. The repeated subproblems are the definition of an overlapping recurrence, and they are exactly what a store removes.

C4.11.1 · part 2

Two stores: a Dictionary and a Map

F# offers two idiomatic ways to hold the store, and the choice is the imperative-shell-versus-pure-core trade in miniature. A mutable System.Collections.Generic.Dictionary, captured in a closure, gives O(1) amortised lookup and insert and reads naturally. An immutable Map, threaded in and out of every call, keeps the recursion pure and referentially transparent at O(log n) per access. Both turn exponential work into one evaluation per distinct subproblem; the Map behind it is the same one from C4.04.

F# — top-down with a mutable Dictionary (verified in FSI)

// the cache lives in a closure; the recursion mutates it in place
open System.Collections.Generic

let memo () =
    let cache = Dictionary<int, int64>()
    let rec fib n =
        if n < 2 then int64 n
        else
            match cache.TryGetValue n with
            | true, v -> v                          // cache hit — O(1)
            | _ ->
                let v = fib (n - 1) + fib (n - 2)
                cache[n] <- v                       // store, then return
                v
    fib
// val memo: unit -> (int -> int64)

let fib = memo ()
fib 40   // val it: int64 = 102334155L  — each of fib 0..40 evaluated once

F# — top-down with an immutable Map, threaded (verified in FSI)

// the cache is a value, threaded in and returned out — the recursion stays pure
let rec waysMemo (cache: Map<int, int>) n : int * Map<int, int> =
    match Map.tryFind n cache with
    | Some v -> v, cache                          // hit — O(log n)
    | None ->
        if n <= 2 then n, cache
        else
            let a, c1 = waysMemo cache (n - 1)
            let b, c2 = waysMemo c1 (n - 2)    // reuse the updated cache
            a + b, Map.add n (a + b) c2
// val waysMemo: cache: Map<int,int> -> n: int -> int * Map<int,int>

let w, _ = waysMemo Map.empty 10
w   // val it: int = 89

Dictionary: a mutable hash map from System.Collections.Generic; O(1) amortised lookup and insert. Captured in a closure so the recursion mutates one cache in place.
Map: F#'s immutable balanced-tree map; O(log n) lookup. Threaded in and out of each call, so no value is ever mutated and the function stays pure.
TryGetValue: the .NET pattern for a lookup-or-miss; in F# it returns a tuple bool * 'T matched as true, v / _.
the trade: the Dictionary is faster and reads naturally; the threaded Map is pure. Both make the work one evaluation per distinct subproblem.

Count the evaluations

Six lessons, each building on the two before it; depth(Lk) = 1 + max(depth of its prerequisites), the same overlapping recurrence. Switch between the plain recursion and the memoised one and count how many times each lesson's depth is evaluated when computing depth(L6). The counts are real — the plain ones are the Fibonacci numbers.

Mode · select one

evaluations: 20

depth(L6): 6

The plain recursion evaluates the deepest-shared lessons many times over — the counts are the Fibonacci numbers, growing with the chain. The store flattens every count to one, so the work is one evaluation per lesson.

C4.11.1 · part 3

Lazy by construction

Because memoisation keeps a demand-driven recursion, it is lazy: it evaluates only the subproblems the target actually depends on, and skips any the target never reaches. That makes it the natural fit when the subproblem space is large but only a sparse part of it is needed for a given query — for instance, the depth of one lesson in a large prerequisite graph. The price is a recursion as deep as the longest chain and a lookup on every call. The next dive turns the same idea inside out: tabulation fills the whole table from the base case up, eager rather than lazy.

a recursion

fib n = fib (n-1) + fib (n-2), re-deriving shared subproblems on every branch.

a recursion plus a store

Each subproblem evaluated once; the rest are lookups. Lazy — only what the target needs.

EchoMQ in F# — memoise the retry schedule

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

The chapter's bus, echo_fs, computes a retry delay from a policy and an attempt count with EchoMQ.Backoff.delayMs. The function is pure and deterministic for the Fixed and Exponential policies, so a consumer that retries repeatedly can memoise the schedule: cache the delay by attempt count, and a repeated attempt-count is a lookup rather than a recompute. The same top-down store this dive teaches applies unchanged.

echo_fs/EchoMQ/Backoff.fs · a memoised schedule

// cache delayMs by attempt count — a repeated attempt is a lookup, not a recompute
let scheduleFor (policy: Backoff.Policy) =
    let cache = Dictionary<int, int>()
    fun attempts ->
        match cache.TryGetValue attempts with
        | true, ms -> ms
        | _ ->
            let ms = Backoff.delayMs policy attempts   // the pure recurrence
            cache[attempts] <- ms
            ms

For Exponential(100, 10000) the first six delays are 100, 200, 400, 800, 1600, 3200 ms; once cached, asking for attempt 3 again is an O(1) read of 400. Because delayMs is deterministic for this policy, the cached value is always correct.

Grounded in echo_fs/EchoMQ/Backoff.fs — built and tested (EchoMQ.Tests/BackoffTests.fs). The Valkey transport EchoMQ.Connector lands next.

The third dive, backoff as dynamic programming, plots this curve from its recurrence. The Jitter policy is the exception — it draws a fresh random value each call, so it is not memoised.

Where this leads

That is solve-each-once from the top down: a recursion plus a store, lazy by construction. The next dive runs the same idea bottom-up — tabulation fills a table from the smallest subproblem to the largest, trading the lookups for a flat pass over an array.

↑ C4.11 · Dynamic programming C4.11.2 · Tabulation → C4.11.3 · Backoff as DP

References

Sources

Microsoft — F# documentation — recursion, closures, and pattern matching.
FSharp.Core API reference — the immutable Map module.
Microsoft — .NET documentation — Dictionary<TKey,TValue> and TryGetValue.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — F4.11.1 · Memoization — the E4 sibling, the same recurrence cached in Elixir.
C4.11 — Dynamic programming — the module hub.
C4.04 — Maps, sets & hashing — the Map behind the cache.
C4 — Algorithms & Data Structures — the chapter.