Memoization vs Tabulation — Filling the Subproblem DAG

The same recurrence, two evaluation strategies. Memoization (left) descends by recursion and caches each subproblem; tabulation (right) fills the table bottom-up in order. Both compute every subproblem exactly once.

step 0

Memoization (top-down, recursion + cache)

computed: 0 cache hits: 0 max depth: 0

Tabulation (bottom-up, ordered table fill)

cells filled: 0 stack used: none order: 0,1,2,…,n
Press Step to begin. Watch the left side recurse and cache while the right side fills its table in strict order — both visiting each subproblem once.
currently computing computed & cached cache hit (reused) base case
Self-contained visualization. The recurrence is fib(n)=fib(n-1)+fib(n-2) (or ways(n)=ways(n-1)+ways(n-2) with ways(0)=ways(1)=1). Both strategies evaluate the identical function over the identical subproblem DAG; memoization is a cached depth-first traversal, tabulation a topological scan. See junior.md and professional.md.