← Learn DSA · Lesson 6 of 11
Recursion & Memoisation
Solve it for a smaller input, then handle the rest.
The idea
A recursive solution needs exactly two things: a base case small enough to answer outright, and a step that makes the problem strictly smaller. If either is missing you get infinite recursion, which is a stack overflow rather than a wrong answer.
The part worth internalising is that recursion is often correct but slow rather than wrong. Naive Fibonacci is a faithful translation of the definition and takes exponential time, because it recomputes the same subproblems along every branch of the call tree.
Memoisation fixes that without changing the shape of the code: cache each result the first time it is computed. The recursion stays readable and the complexity collapses, usually from exponential to linear in the number of distinct subproblems.
That is also the bridge to dynamic programming. Memoised recursion is top-down DP; filling a table iteratively is the same computation bottom-up.
Walkthrough
Recursion unwinding: each call reads one element, then the answers add back up as the stack collapses.
What it costs
- time
- Depends on the recurrence — O(number of distinct subproblems) once memoised
- space
- O(depth) for the call stack, plus O(subproblems) for the cache
Memoisation does not make the algorithm cleverer. It stops it repeating itself, which for a branching recurrence is the difference between 2^n and n.
When to reach for it
- The problem is naturally defined in terms of itself.
- The structure is a tree or a graph, where the code mirrors the shape of the data.
- You are exploring choices, each leaving a smaller version of the same problem.
- A recursive formulation is obviously correct and you can memoise it afterwards.
Rather than the obvious alternative
An explicit stack
Same traversal without a call-stack limit. Prefer it when the depth could reach tens of thousands, or when you need to pause and resume.
Iteration
A loop is usually faster and always avoids stack overflow. Recursion earns its cost when the alternative is bookkeeping you would otherwise write by hand.
Bottom-up DP
Once memoised, recursion is DP with a call stack. The bottom-up form avoids the stack entirely and is often easier to space-optimise.
How to spot it
- The problem is naturally defined in terms of itself.
- You are exploring choices where each choice leaves a smaller version of the same problem.
- The structure is a tree or a graph.
- A brute-force recursion is obvious but too slow, and the same arguments keep recurring.
Where it goes wrong
A base case that is never reached
Every path must shrink towards it. A branch that does not is an infinite loop with extra steps.
Caching on the wrong key
The key must capture everything the result depends on. Miss a parameter and the cache returns a confidently wrong answer.
Deep recursion on large inputs
Python's default limit is around 1000 frames. A linear recursion over a big array will hit it — iterate instead.
Practise it
Build it
The problems above are one function each. These assemble the same ideas into a working thing across several files.