Top-down / Bottom-up

Recursive
vs Sequential

The same dynamic programming problem, solved two ways. Watch memoization prune the recursion tree — then watch tabulation fill an array, left to right.

Top-down → Bottom-up →
↓

01 — Top-down

Recursive with memoization

Start at the top and recurse down. The first time a subproblem is seen it computes; the next time, it returns from a cache. Watch repeated branches get pruned.

fib(5)
fib(4)
fib(3)HIT
fib(3)
fib(2)HIT
fib(2)
fib(1)HIT
fib(1)
fib(0)
computing cache hit

02 — Bottom-up

Sequential tabulation

No recursion, no stack. Just an array filled from smallest to largest — each entry built directly from the two before it.

03 — Trade-offs

Same answer, different paths

Both compute the exact same DP table — one grows the table lazily from the top, the other builds it eagerly from the bottom.

Recursive (memoized)

top-down
  • → Solves only subproblems actually needed.
  • → Natural to write: just add a cache to plain recursion.
  • → Uses call-stack memory (O(n) depth).
  • → Can hit recursion limits on large n.

Time

O(n)

Space

O(n) cache + stack

Sequential (tabulated)

bottom-up
  • → Fills every cell in a predictable order.
  • → No stack — just a loop and an array.
  • → Can often be space-optimized (rolling array).
  • → The order must be worked out ahead of time.

Time

O(n)

Space

O(n) table

The recursive memo and the sequential table hold the exact same values. They differ only in direction of construction.