Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Base cases F(0)=0, F(1)=1; else `fib(n-1) + fib(n-2)`. Naive is O(2ⁿ); add a memo array/map for O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you spot overlapping subproblems and apply memoisation.
Where candidates slip
Shipping the exponential recursion.
How to stand out
Offer top-down memoisation and the O(1)-space iterative roll.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Two-branch recursion (+ memo)
1Hint 1Explore hintHide hint
Write the two-base-case recurrence first.
2Hint 2Explore hintHide hint
Sketch the call tree — which subproblems repeat?
3Hint 3Explore hintHide hint
Cache results (memoise) to collapse O(2ⁿ) to O(n).
A · Core idea
F(n) = F(n−1) + F(n−2), with two base cases F(0)=0, F(1)=1. The naive recursion is the canonical example of overlapping subproblems causing exponential blow-up — and memoisation is the expected fix.
Why it's O(2ⁿ). The two recursive branches re-evaluate the same values repeatedly: computing F(5) recomputes F(3) twice, F(2) three times, and so on. The call tree roughly doubles each level, so the work is exponential. F(50) naively makes billions of calls.
The fix: memoisation. Cache each F(k) the first time it's computed (an array or hash map, or @lru_cache). Subsequent calls hit the cache in O(1), collapsing the whole thing to O(n). Iteration (rolling two variables) is the O(1)-space alternative.
The real interview point is recognising the exponential blow-up and removing it — not writing the recurrence.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5 (naive call tree)F(5)
F(4)+F(3)
branches5C · Code with teaching comments
D · Why it works and complexityO(2ⁿ) naive, O(n) memoised timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The interview point isn't the recurrence — it's recognising the exponential blow-up and fixing it with memoisation or iteration.
ComplexityO(2ⁿ) naive, O(n) memoised time, O(n) space — naive recursion's call tree doubles each level → O(2ⁿ); memoising computes each F(k) once → O(n).
E · Edge cases and pitfalls5n = 0 — Base case → 0.Explore edge casesHide edge cases
Edge cases handled
n = 0Base case → 0.n = 1Base case → 1.n = 50Naive times out; memoised is instant.
Pitfalls
- Leaving the naive O(2ⁿ) version for large n.
- Only one base case, mishandling n = 0 or 1.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long fib(int n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); } // Memoised: cache results in a long[] indexed by n.Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Naive recursion without memo
Recomputing F(n-1) and F(n-2) re-evaluates shared subproblems exponentially.
Explore the code comparisonHide the code comparison
Naive recursion without memo
Recomputing F(n-1) and F(n-2) re-evaluates shared subproblems exponentially.
Don't write this
def fib(n):
if n<2: return n
return fib(n-1)+fib(n-2) # O(2^n)Write this instead
from functools import lru_cache
@lru_cache(None)
def fib(n):
if n<2: return n
return fib(n-1)+fib(n-2) # O(n)Revise
Carry the pattern into the interview
Pattern to remember
Overlapping subproblems → memoise
Code pattern to memorize
F(n)=F(n-1)+F(n-2); MEMOISERules to remember
- 1F(0)=0, F(1)=1.
- 2Naive is exponential.
- 3Memoise → O(n).
Use this pattern when
- Demonstrating memoisation
- Overlapping-subproblem recursions
Choose another pattern when
- Naive recursion on large n
Interview takeaway
Recursion with repeated subproblems begs for memoisation.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA core fresher pattern: Overlapping subproblems → memoise. Master it on small inputs and it transfers to harder problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Nth Fibonacci NumberIterative O(n)/O(1) version.
- Climbing StairsComing soonSame recurrence as a DP.