Fibonacci Memoization Java | Fresher Interview
Fast recall
Quick revision
Core answer
fib(5) calculates fib(3) twice and fib(2) three times. Memoization caches results in a HashMap or array, collapsing the tree and cutting time from O(2^n) to O(n) at the cost of O(n) space.Understanding of exponential blowup and the memoization fix — this is the intro to dynamic programming
Not being able to explain WHY it's O(2^n) — memorizing the fact without understanding the recursion tree
Draw the recursion tree to show duplicate subproblems, then show how memoization collapses it to O(n)
Interview-ready guide
Interview answer
Naive recursive Fibonacci is O of two to the n because it recomputes the same values over and over.
Let me show you why with fib of five. That calls fib of four and fib of three. Fib of four calls fib of three and fib of two.
So fib of three gets called twice already. And fib of two gets called three separate times. Every level of recursion roughly doubles the number of calls, creating a binary tree that explodes exponentially.
For fib of forty, you're making over a billion calls when you only need forty unique computations. Memoization fixes this by caching results. You use a HashMap where the key is n and the value is fib of n.
The first time you compute fib of three, you store it. Every future call to fib of three just looks up the cached value instead of recursing again. This collapses the exponential tree into a linear chain of work.
Now you compute each fib of k exactly once, making it O of n time. The tradeoff is you use O of n space for the cache. In code, you check if the cache contains n before recursing.
If it does, return the cached value immediately. If not, recurse to compute it, store it in the cache, then return it. The common mistake is not checking the cache first — freshers sometimes add a HashMap but forget the containsKey check, so they recompute everything anyway and get no speedup.
This memoization pattern is the foundation of dynamic programming. It's called top-down DP because you start with the big problem and break it down, caching as you go.
For example, while finding fib(5), the naive tree asks for fib(3) from more than one branch. After the first result is cached, the next call reads that value directly; only fib(0) through fib(5) need to be solved.
Fibonacci Memoization Java | Fresher Interview
Direct Answer
Naive Fibonacci recomputes the same subproblems, forming a binary tree of redundant work — computing fib(5) calculates fib(3) twice and fib(2) three times. Memoization caches results in a HashMap or array, collapsing the tree and cutting time from O(2^n) to O(n) at the cost of O(n) space.
Deep Dive & Architecture
The naive recurrence creates two calls for most values: fib(n - 1) and fib(n - 2). Those branches overlap. In the call tree for fib(5), fib(3) is reached from both fib(4) and the top-level fib(3) branch, and smaller values repeat even more often.
Memoization adds one rule before recursion: if fib(n) is already cached, return it immediately. Otherwise compute it once, store it, and reuse it later.
Worked example
The first path computes fib(2) = 1, then fib(3) = 2, then fib(4) = 3. When another branch requests fib(3), the cache returns 2 without opening new calls. Finally fib(5) stores 5. Only the states from 0 through 5 are needed.
There are n distinct non-base states and each does constant work after its two dependencies are available, so the time becomes O(n). The cache needs O(n) space, and top-down recursion also keeps O(n) call-stack frames in the worst case. A bottom-up loop can keep only the previous two values and reduce extra space to O(1) when the intermediate results are not otherwise needed.
Code Example
import java.util.HashMap;
import java.util.Map;
public class FibonacciDemo {
// Naive: O(2^n) time, recomputes subproblems
public static int fibNaive(int n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2); // exponential branching
}
// Memoized: O(n) time, O(n) space
public static int fibMemo(int n, Map<Integer, Integer> cache) {
if (n <= 1) return n;
if (cache.containsKey(n)) return cache.get(n); // cache hit
int result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
cache.put(n, result); // store for reuse
return result;
}
public static void main(String[] args) {
System.out.println(fibMemo(40, new HashMap<>())); // instant: 102334155
}
}
// Dry run fib(5): fib(4)+fib(3); fib(4) reuses cached fib(3) and fib(2)
// -> 5 unique computations instead of 15 calls.
Common Mistakes & Pitfalls
- Not understanding the recursion tree: freshers say Fibonacci is O(2^n) because they were told, but can't draw the tree. Sketch fib(5) — fib(3) appears twice, fib(2) three times.
- Using a cache but not checking it first: adding a HashMap but forgetting the
containsKeycheck means you recompute and overwrite each time, gaining nothing. - Not initializing the cache: passing null or forgetting to create the HashMap causes a
NullPointerException.
Check your understanding
Answer these without looking back at the article.
- What is recursion and what are its two essential components?
- How do you use recursion to generate all permutations of a string?
- What is tail recursion and does Java optimize it?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.