How does dynamic programming differ from recursion and memoization?
Dynamic programming (DP) is an algorithmic strategy for problems with overlapping subproblems and optimal substructure. Recursion is a control-flow technique in which a function calls itself, while memoization caches previously computed results and can be used to implement top-down DP.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Key Differences
| Approach | How it works | Typical use |
|---|---|---|
| Plain recursion | A function calls itself until it reaches a base case | Tree traversal, factorials, backtracking |
| Memoized recursion | Recursion is combined with a cache so repeated states are computed once | Top-down DP for problems with overlapping subproblems |
| Bottom-up DP | States are computed iteratively in dependency order | DP when recursion depth is large or all states are needed |
-
Recursion describes how control flow is organized; it does not imply exponential time.
-
Dynamic programming describes how the algorithm avoids repeated work, usually through either top-down memoization or bottom-up tabulation.
-
Memoization is a caching technique, not a synonym for DP. It can be applied to a recursive function, but a memoized solution is DP only when its states, dependencies, and recurrence form a valid DP decomposition.
-
Bottom-up DP does not use recursion, so it avoids Python’s recursion-depth limit.
How It Works
A DP solution identifies:
-
State: The information required to solve one subproblem.
-
Recurrence: How the current state is calculated from smaller states.
-
Base cases: The states that require no further calculation.
-
Evaluation order: Whether dependencies are calculated on demand with memoization or iteratively from smaller states.
For Fibonacci, the recurrence is F(n) = F(n - 1) + F(n - 2) for n >= 2, with F(0) = 0 and F(1) = 1.
A memoized evaluation of fibonacci(5) proceeds as follows:
-
fibonacci(5) -
fibonacci(4)-
fibonacci(3) -
fibonacci(2)-
fibonacci(1)computes1 -
fibonacci(0)computes0
-
-
fibonacci(1)returns the cached1 -
fibonacci(2)returns the cached1
-
-
fibonacci(3)returns the cached2
Each unfinished recursive call occupies one activation record on the call stack. Python’s default recursion limit is approximately 1,000, and Python has no tail-call optimization, so deeply nested inputs may require bottom-up evaluation or an explicit stack.
To convert recursive memoization to an explicit stack, push each state together with a marker indicating whether it has been expanded. On the first visit, push the marker and its dependencies; when the expanded marker is reached, compute the state from its now-cached dependencies. This avoids the recursion limit, although the memoization cache still requires space.
In Python, functools.cache provides memoization for hashable arguments. The cache key must include every argument that affects the result.
Complexity
For Fibonacci, let n be the input and phi be the golden ratio:
| Approach | Best time | Average time | Worst time | Auxiliary space |
|---|---|---|---|---|
| Plain recursion | O(phi^n) |
O(phi^n) |
O(phi^n) |
O(n) for the call stack |
| Memoized recursion | O(n) |
O(n) |
O(n) |
O(n) cache plus O(n) stack |
| Bottom-up DP | O(n) |
O(n) |
O(n) |
O(1) for Fibonacci |
| Explicit-stack memoization | O(n) |
O(n) |
O(n) |
O(n) cache plus O(n) stack |
These are auxiliary complexities and do not count the input itself. Memoized recursion and bottom-up DP take O(n) time because each Fibonacci state is computed once. Plain recursion takes O(phi^n) because it repeatedly evaluates overlapping states.
For a general top-down DP problem, let R be the number of reachable states, C the maximum number of transitions per state, and d the maximum recursion depth. Under the standard constant-time-average cache lookup assumption, evaluation takes O(R × C) time and at most O(R + d) auxiliary space. The best case is O(1) when the requested state is already a base case. With adversarial hash collisions, a strict dictionary-based worst case can degrade to O(R² × C).
A bottom-up evaluation of N possible states takes O(N × C) time and O(N) auxiliary space in the full-evaluation case; a rolling-state optimization may reduce the space to O(k), where k is the number of retained states.
Common Pitfalls
-
Confusing recursion with DP: Recursion is a mechanism; overlapping subproblems and a well-defined recurrence are what justify DP.
-
Using an incomplete state: Omitting information that affects the answer can produce incorrect cache hits.
-
Caching mutable arguments: Mutating a value after it has been cached can make the cached result incorrect.
-
Ignoring base cases: An incorrect base case can cause infinite recursion or an incorrect result.
-
Exceeding Python’s recursion limit: Use bottom-up DP or an explicit stack for deep inputs.
-
Ignoring problem-specific edge cases: For Fibonacci,
n = 0andn = 1are base cases, while negative inputs should be rejected.
Interviewers commonly follow up by asking for the DP state and recurrence, a comparison of top-down and bottom-up implementations, or a proof that the recurrence uses optimal substructure.