DP vs Recursion —
The full before/after, side by side.
Every lesson in this hub has shown one piece of this story — naive recursion recomputing overlapping subproblems, and DP fixing it with a cache or a table. This page puts the two extremes directly next to each other: naive fib(30) versus memoized fib(30). Run both on LearnBug and watch millions of redundant calls collapse into 30.
What's actually different between them?
Nothing about the mathematical definition changes — fib(n) = fib(n-1) + fib(n-2) either way. The only difference is whether previously-computed results are remembered. Naive recursion forgets everything between calls; DP (whether top-down/memoized or bottom-up/tabulated) remembers, and that single difference is what separates exponential time from linear time.
Why visualization helps
A call count like "2.7 million vs 30" is just a number until you watch it happen. LearnBug can run both versions on the same input and show the actual call count climbing in real time — the naive version's counter spins for a noticeable moment while the memoized one finishes instantly, at the exact same input.
Top-down memoization vs bottom-up tabulation
Naive recursion — no memory
The straightforward recursive definition, called directly. Simple to write, exponential to run once overlapping subproblems exist.
Top-down (memoization) — still recursive
Same recursive structure as naive, plus a cache. Easiest to convert to from a naive solution — usually just wrapping it and adding a dictionary check.
Bottom-up (tabulation) — no recursion at all
Builds an array iteratively from the base cases upward. No call stack growth, no recursion-limit risk — see Climbing Stairs for a full example.
fib(20): naive vs memoized call counts
Naive fib(20): the call tree branches into 21,891 total calls
Every call spawns two more (except base cases), and the same smaller values — fib(10), fib(5), fib(2) — get recomputed from scratch dozens or hundreds of times across different branches.
Memoized fib(20): exactly 21 unique computations (fib(0) through fib(20))
Every value from 0 to 20 is computed exactly once, cached, and reused for every later request. The recursive structure is identical to naive — only the redundant recomputation is gone.
The gap widens explosively: fib(30) naive is ~2.7M calls, fib(40) naive is ~330M
Memoized (or tabulated) stays linear the whole way — fib(30) is 31 computations, fib(40) is 41. The naive version's cost doubles roughly every time n increases by 1; the DP version's cost barely moves.
Both return the exact same numeric answer at every n — DP changes cost, never correctness
This is worth stating explicitly: memoization and tabulation don't change what problem is being solved or what answer comes out — only how much work it takes to get there.
Same answer, radically different cost: that's the entire value proposition of DP
Naive and memoized, run on the same input
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2) # O(2^n) — no memory
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) # O(n) — cached
return memo[n]
print(fib_naive(20)) # same answer
print(fib_memo(20)) # same answer, far fewer callsComplexity Notes
Frequently asked questions
How do I know if a recursive problem can benefit from DP?
Check for two properties: overlapping subproblems (the same smaller input recurs across different branches of the recursion — like fib(3) appearing twice) and optimal substructure (the best solution to the whole problem can be built from best solutions to its subproblems). If both hold, memoization or tabulation will help; if subproblems never actually overlap, there's nothing to cache.
Should I always prefer bottom-up over top-down?
Not necessarily — top-down (memoization) is often easier to write correctly because it mirrors the natural recursive definition, and it only computes subproblems that are actually needed. Bottom-up (tabulation) avoids recursion overhead and stack-depth risk entirely, but sometimes computes more states than strictly necessary. Both reach the same O(n) complexity for problems like Fibonacci.
Why does naive Fibonacci become impractical so quickly?
Because the call count roughly doubles with each increment of n — the classic signature of exponential growth. fib(20) is manageable (~22,000 calls), fib(30) is noticeably slow (~2.7M calls), and fib(40) (~330M calls) can take tens of seconds — all for a function whose memoized version handles any of these instantly.
Does every problem in this hub follow the naive-to-DP pattern shown here?
Yes, in spirit — Climbing Stairs, Coin Change, and 0/1 Knapsack all have a naive recursive formulation that would recompute overlapping subproblems, and all are solved here with a DP table (bottom-up) for exactly that reason. Recognizing "this recursive definition has overlapping subproblems" is the transferable skill across all of them.
Watch millions of redundant calls collapse into a handful
Paste naive and memoized versions into LearnBug and compare the call counts directly.