Skip to interview prep
Apexed

364. How do you turn a recursive recurrence into memoised code, and when does it help?

EasyDynamic programming

Technical
Show model answer

Identify the state (the parameters that fully determine a subproblem's answer), write the recursive function directly from the recurrence, and add a cache keyed by the state: check it before computing and store the result after. Running time becomes (number of distinct states) × (work per state, excluding recursive calls). Space is the cache plus the recursion depth.

Memoisation only helps when subproblems overlap. Naive Fibonacci makes about φ^n calls, but with a cache it makes O(n) calls. Merge sort's subproblems never repeat, so caching gains nothing. Watch out for hidden state, such as a global variable or a mutable list the function reads, which must become part of the cache key or the memo returns wrong answers.

How do you turn a recursive recurrence into memoised code, and when does it help — Data structures & algorithms interview question — Apexed