Memoization & overlapping subproblems

Every lesson sits at the end of a chain of prerequisites, and the Portal wants the longest such chain — how deep a learner must go before reaching it. depth(lesson) is one plus the deepest of its prerequisites, which is naturally recursive. The catch is that prerequisites are shared, so a plain recursion re-derives the depth of a popular prerequisite once for every path that passes through it. Memoisation caches each lesson’s depth the first time it is computed, and every later visit is a lookup.

Six lessons, each building on the two before it. Switch between the plain recursion and the memoised one and count how many times each lesson’s depth is evaluated.

Count the evaluations Advanced: lazy by construction

Count the evaluations

To find depth(L6) the recursion asks its prerequisites, which ask theirs. Without a cache the shared lessons near the bottom are re-evaluated along every path that reaches them; with one, each is evaluated once and then served from the cache. Switch the mode.

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 cache flattens every count to one, so the work is one evaluation per lesson.

Advanced: lazy by construction

Memoisation keeps the recursion exactly as written and threads a cache through it: before computing depth(lesson), check the cache; after, store it. Because it is still a recursion driven by demand, it is lazy — it only ever evaluates the prerequisites that the target actually depends on, and skips any lesson no path reaches. That makes it a natural fit when the subproblem space is large but only a sparse part of it is needed for a given query, which is exactly the shape of a prerequisite graph.

The price is a recursion as deep as the longest chain and a cache lookup on every call. In a pure language the cache is a value, so it is threaded in and out of each call rather than mutated — or parked in a small Agent or process dictionary when threading is noisy. Either way the cache is one of this chapter’s maps, and the recurrence below is the same one the hub counted, now reading depths off a prerequisite graph instead of pacings off a track.

# longest prerequisite chain to a lesson, with a threaded cache
def depth(lesson, cache) do
  case cache do
    %{^lesson => d} -> {d, cache}                       # cache hit — O(1)
    _ ->
      {d, cache} =
        lesson
        |> Catalog.prerequisites()
        |> Enum.reduce({0, cache}, fn p, {mx, c} ->
          {dp, c} = depth(p, c)                       # recurse, reusing the cache
          {max(mx, dp), c}
        end)
      {d + 1, Map.put(cache, lesson, d + 1)}   # store and return
  end
end

a recursion

depth(l) = 1 + max(depth(prereqs)), re-deriving shared lessons.

a recursion plus a cache

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

Next: tabulation — the same solve-each-once from the bottom up, filling a table instead of caching a recursion.

References

Primary sources for this lesson, and where it connects in the course.

Sources

Memoization — Wikipedia — caching a recursion by argument.
Overlapping subproblems — Wikipedia — why the plain recursion repeats work.
Elixir — Agent — a place to park a cache when threading is noisy.

Related in this course

F4.11 · Dynamic programming & advanced problems — the module hub.
F4.04 · Maps, sets & hashing — the map behind the cache.
F4 · Algorithms & Data Structures