SpaceComplexity

DP vs Memoized Recursion: Complexity, Tradeoffs, and When to Use Each

June 10, 20269 min read
dsaalgorithmsinterview-prepdynamic-programming
DP vs Memoized Recursion: Complexity, Tradeoffs, and When to Use Each
TL;DR
  • Both approaches share identical time complexity in standard DP problems — each subproblem is computed exactly once
  • Memoized recursion carries two simultaneous space costs: the memo table and the call stack depth, with no way to compress either
  • Tabulation unlocks rolling array optimization, collapsing O(n) to O(1) or O(m×n) to O(min(m,n)) — memoization cannot do this
  • Python's 1,000-frame default limit makes memoized recursion unsafe for large n; tabulation has no recursion depth risk
  • Memoization skips unreachable states in sparse subproblem graphs; tabulation fills every cell regardless
  • Use memoization when the recurrence maps cleanly to recursion; switch to tabulation when stack depth or space compression matters

You have two approaches. Both visit each subproblem once. Both cache the result. Both get the right answer. One will casually blow up at n=2000 and print RecursionError: maximum recursion depth exceeded in comparison while you stare at it in disbelief during an interview.

What separates DP from memoized recursion is whether your solution survives large inputs, how much space you can recover, and how fast you can actually write the thing under pressure.

Most explanations stop at "top-down uses recursion, bottom-up uses a table." True, but unhelpful. That skips the execution model, the complexity analysis, and where the tradeoffs actually bite you.

Same Problem, Different Control Flow

Dynamic programming works by caching subproblem results so you never compute the same thing twice. Both approaches implement that idea. The difference is which direction you walk the subproblem graph.

Memoized recursion (top-down): start from the target problem, recurse into subproblems, store results on the way back up. You discover which subproblems you need as you go.

Tabulation (bottom-up): start from the smallest base cases, fill a table in dependency order, never recurse. You compute every cell in the table, whether you need it or not.

The cache in both cases is conceptually identical. Memoization is demand-driven: it only computes subproblems it actually visits. Tabulation is supply-driven: it fills every state up front.

Fibonacci: The Side-by-Side

# Memoized recursion
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# Bottom-up tabulation
def fib_dp(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Same answer. Same O(n) time. The execution looks nothing alike.

Memoized recursion builds a call tree and caches hits on revisit:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) [cache hit]
│   └── fib(2) [cache hit]
└── fib(3) [cache hit]

Tabulation fills an array left to right, no recursion involved:

i:    0   1   2   3   4   5
dp: [ 0,  1,  1,  2,  3,  5 ]
      ^   ^   ^   ^   ^   ^
      base   computed in order

The call tree has O(n) frames alive simultaneously on the call stack. The table has none.

Same Time, Different Space

Time: Usually Identical

In almost every standard DP problem, both approaches have the same time complexity. Each subproblem is computed once.

For Fibonacci: O(n) either way. For Longest Common Subsequence: O(m × n) either way. For 0/1 Knapsack: O(n × W) either way.

The one exception: problems where the dependency graph is sparse. If only a fraction of states are reachable from your starting point, memoization computes fewer states. Tabulation fills the whole table regardless.

Space: This Is Where They Split

Here's the part most tutorials gloss over because it's slightly uncomfortable.

Memoized recursion uses:

  • O(states) for the memo table
  • O(max recursion depth) for the call stack

Both costs are active simultaneously. For Fibonacci(n), you pay O(n) for the cache and O(n) for the call stack. Actual memory usage is roughly 2 × O(n). Not a disaster for small n. A problem when n starts getting ambitious.

Tabulation uses:

  • O(states) for the DP table
  • O(1) extra if you apply rolling arrays

For Fibonacci, that O(n) table collapses to O(1):

def fib_optimized(n: int) -> int:
    if n <= 1:
        return n
    prev, curr = 0, 1
    for i in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

You cannot do the rolling array trick with memoized recursion. The call stack holds references back through the entire call chain. Space optimization is a tabulation-only capability.

Call stack depth vs table: memoized recursion stacks O(n) frames while tabulation needs O(1)

Stack Overflow Is Not a Hypothetical

Python's default recursion limit is 1,000 frames. One thousand:

>>> fib_memo(2000)
RecursionError: maximum recursion depth exceeded in comparison

You can raise it with sys.setrecursionlimit(), but the OS stack has a hard ceiling: 8 MB on Linux, 512 KB on macOS threads. A frame typically takes 64 to 128 bytes. That gives you roughly 4,000 to 65,000 frames before you hit the wall, depending on platform and frame size.

Java and C++ have similar limits. Go's goroutine stacks grow dynamically, which helps. You still pay for the growth.

For large n, tabulation is the only safe option. There's no recursion depth to worry about. The loop just runs. It doesn't know about limits. It doesn't care about your OS. It fills the table and goes home.

Worked Example: Coin Change

Given coins = [1, 5, 10] and amount = 11, find the fewest coins needed.

# Memoized recursion
from functools import lru_cache

def coin_change_memo(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def dp(remaining: int) -> int:
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return 1 + min(dp(remaining - c) for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

# Tabulation
def coin_change_dp(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Both: O(amount × len(coins)) time, O(amount) space.

The memoized version reads like the problem statement. You ask "what's the minimum for amount=11?" and the recursion handles the rest. The tabulation version forces you to think about fill order explicitly: every cell i must be computed before any cell that depends on it, which means left to right.

That's either a feature or a tax depending on your mood.

Worked Example: Longest Common Subsequence

LCS of "abcde" and "ace" is "ace", length 3.

# Memoized recursion
from functools import lru_cache

def lcs_memo(s1: str, s2: str) -> int:
    @lru_cache(maxsize=None)
    def dp(i: int, j: int) -> int:
        if i == len(s1) or j == len(s2):
            return 0
        if s1[i] == s2[j]:
            return 1 + dp(i + 1, j + 1)
        return max(dp(i + 1, j), dp(i, j + 1))
    return dp(0, 0)

# Tabulation
def lcs_dp(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Both: O(m × n) time. The table fill:

      ""  a  c  e
  ""   0  0  0  0
  a    0  1  1  1
  b    0  1  1  1
  c    0  1  2  2
  d    0  1  2  2
  e    0  1  2  3

Each cell depends only on the cell above, the cell to the left, and the cell diagonally above-left. Fill row by row and you respect all dependencies. It's methodical in a way that's almost soothing.

With tabulation, you can compress this to O(min(m, n)) space by keeping only two rows. The memoized version uses O(m × n) for the cache plus O(m + n) for the call stack depth, with no way to compress either. The memoized version is doing the same work and paying more for parking.

The Space Optimization Pattern

Rolling arrays are a tabulation-only technique. For 0/1 Knapsack, the table is O(n × W). With rolling arrays, it drops to O(W):

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for j in range(capacity, w - 1, -1):  # backward scan
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

The backward scan is subtle. Forward iteration would reuse the same item multiple times within a single pass, turning 0/1 knapsack into unbounded knapsack. A one-line direction change, a completely different problem.

This kind of dependency insight is visible in the tabulation fill order and invisible in memoized recursion. You can write the memoized version without ever noticing the distinction. The table forces you to reckon with it. See the full analysis in Bottom-Up Dynamic Programming.

Which One to Reach For

Use memoized recursion when:

  • The recurrence has complex branching that's easier to express recursively
  • Only a sparse subset of states gets visited (irregular graphs, tree path problems)
  • You want to write and verify the solution quickly
  • n is small enough that the call stack is safe (roughly under 500 in Python, under 5,000 in Java/C++)

Use tabulation when:

  • n is large and stack overflow is a real risk
  • You need rolling array space optimization
  • You need to reconstruct the full solution path from the table
  • You want to eliminate function call overhead in a tight loop

One more thing: tabulation forces you to get the fill order right, which surfaces dependency bugs that memoization papers over. If you fill a cell before its dependencies are ready, you get wrong answers. That discipline is a feature, not a cost. Memoization will happily hide this from you until production.

What to Say During a Tabulation Fill

Reach for whichever you can implement correctly under time pressure. Memoized recursion is usually faster to write because the code mirrors the recursive problem definition. Convert to tabulation when the interviewer asks about space optimization or mentions stack overflow as a constraint.

If you practice on SpaceComplexity with voice-based mock interviews, work on narrating your fill order out loud. "I'm filling from smaller subproblems to larger ones, left to right, because dp[i] depends only on dp[i - coin]" is the level of narration that earns a Strong Hire on Communication. Silence during a tabulation fill loses signal even when the code is correct. The interviewer is watching you fill a table and hearing nothing. That's not confidence. That's a wall.

For a deeper look at recognizing which problems need DP at all, see How to Recognize Dynamic Programming Problems. For the full complexity analysis of memoization, including the states × work-per-state formula, see Memoization Time Complexity.

Further Reading