Memoization to Optimize Recursion in DSA Java

Mental Model

Memoization remembers answers to small problems so we don't solve them again.

Analogy: Imagine solving a puzzle and writing down each step's answer on sticky notes. Next time you see the same step, you just read the note instead of solving again.

call fib(4)
  ↓
call fib(3) ← memo: {}
  ↓
call fib(2)
  ↓
call fib(1) -> returns 1
memo: {1=1}
  ↑
call fib(2) again? Check memo first -> use saved answer

Dry Run Walkthrough

Input: Calculate fib(4) using recursion with memoization

Goal: Compute fib(4) efficiently by storing intermediate results to avoid repeated work

Step 1: Call fib(4), memo is empty

fib(4) -> memo: {}

Why: Start computing fib(4), no answers saved yet

Step 2: Call fib(3) inside fib(4), memo still empty

fib(4) -> fib(3) -> memo: {}

Why: Need fib(3) to compute fib(4)

Step 3: Call fib(2) inside fib(3), memo still empty

fib(4) -> fib(3) -> fib(2) -> memo: {}

Why: Need fib(2) to compute fib(3)

Step 4: Call fib(1) inside fib(2), base case returns 1, store in memo

fib(4) -> fib(3) -> fib(2) -> fib(1)=1 -> memo: {1=1}

Why: fib(1) is base case, save result

Step 5: Call fib(0) inside fib(2), base case returns 0, store in memo

fib(4) -> fib(3) -> fib(2) -> fib(0)=0 -> memo: {1=1, 0=0}

Why: fib(0) is base case, save result

Step 6: Calculate fib(2) = fib(1) + fib(0) = 1 + 0 = 1, store in memo

fib(4) -> fib(3) -> fib(2)=1 -> memo: {1=1, 0=0, 2=1}

Why: fib(2) computed and saved to avoid recomputation

Step 7: Call fib(1) inside fib(3), found in memo as 1, reuse it

fib(4) -> fib(3) -> fib(1)=1 (from memo) -> memo: {1=1, 0=0, 2=1}

Why: Reuse saved fib(1) to save time

Step 8: Calculate fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store in memo

fib(4) -> fib(3)=2 -> memo: {1=1, 0=0, 2=1, 3=2}

Why: fib(3) computed and saved

Step 9: Call fib(2) inside fib(4), found in memo as 1, reuse it

fib(4) -> fib(2)=1 (from memo) -> memo: {1=1, 0=0, 2=1, 3=2}

Why: Reuse saved fib(2) to save time

Step 10: Calculate fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store in memo

fib(4)=3 -> memo: {1=1, 0=0, 2=1, 3=2, 4=3}

Why: fib(4) computed and saved

Result:

fib(4)=3 -> memo: {0=0,1=1,2=1,3=2,4=3}

Annotated Code

DSA Java

import java.util.HashMap;
import java.util.Map;

public class MemoizationFib {

    // Recursive Fibonacci with memoization
    public static int fib(int n, Map<Integer, Integer> memo) {
        if (memo.containsKey(n)) {
            return memo.get(n); // reuse saved answer
        }
        if (n <= 1) {
            memo.put(n, n); // base case: fib(0)=0, fib(1)=1
            return n;
        }
        int result = fib(n - 1, memo) + fib(n - 2, memo); // sum of two previous
        memo.put(n, result); // save computed result
        return result;
    }

    public static void main(String[] args) {
        Map<Integer, Integer> memo = new HashMap<>();
        int n = 4;
        int result = fib(n, memo);
        System.out.println("fib(" + n + ") = " + result);
        System.out.println("Memo contents: " + memo);
    }
}

if (memo.containsKey(n)) {

Check if answer for n is already saved to avoid recomputation

if (n <= 1) {

Handle base cases fib(0)=0 and fib(1)=1

int result = fib(n - 1, memo) + fib(n - 2, memo);

Recursively compute fib(n) as sum of fib(n-1) and fib(n-2)

memo.put(n, result);

Save computed result for n to memo

Output

fib(4) = 3

Memo contents: {0=0, 1=1, 2=1, 3=2, 4=3}

Complexity Analysis

Time: O(n) because each fib number from 0 to n is computed once and then reused

Space: O(n) for the memo map storing results for each number up to n

vs Alternative: Without memoization, time is O(2^n) due to repeated calls; memoization reduces it to linear time

Edge Cases

n = 0 (smallest input)

Returns 0 immediately from base case

DSA Java

if (n <= 1) {

n = 1 (smallest non-zero input)

Returns 1 immediately from base case

DSA Java

if (n <= 1) {

Repeated calls with same n

Memo returns saved result instantly without recursion

DSA Java

if (memo.containsKey(n)) {

When to Use This Pattern

When you see a recursive problem with overlapping subproblems, reach for memoization to save repeated work and speed up the solution.

Common Mistakes

Mistake: Not checking memo before recursive calls, causing repeated work
Fix: Always check if the answer is in memo before computing recursively

Mistake: Not saving computed results in memo after recursion
Fix: Store the computed result in memo before returning

Summary

Memoization stores results of recursive calls to avoid repeating work.

Use it when recursion solves the same subproblems multiple times.

The key is to check and save answers in a map before and after recursion.

Practice

1. What is the main purpose of using memoization in recursive functions?

easy

A. To store results of expensive function calls and reuse them

B. To make the code shorter and simpler

C. To avoid using loops in recursion

D. To increase the number of recursive calls

Solution

1. Step 1: Understand recursion inefficiency

   Recursive functions often repeat the same calculations multiple times, which wastes time.

2. Step 2: Role of memoization

   Memoization saves the results of these repeated calculations so they can be reused instead of recalculated.

3. Final Answer:

   To store results of expensive function calls and reuse them -> Option A

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated results to speed recursion [OK]

Common Mistakes:

• Thinking memoization makes code shorter
• Confusing memoization with iteration
• Believing memoization increases recursion calls

2. Which of the following Java code snippets correctly declares a memoization cache for storing integer results by input integer keys?

easy

A. Map memo = new HashMap<>();

B. List<Integer> memo = new ArrayList<>();

C. int[] memo = new int();

D. HashSet<Integer> memo = new HashSet<>();

Solution

1. Step 1: Identify suitable data structure for key-value pairs

   Memoization requires storing results by input keys, so a Map is ideal.

2. Step 2: Check Java syntax correctness

   Map memo = new HashMap<>(); uses Map with HashMap, which is correct syntax for memoization cache.

3. Final Answer:

   Map memo = new HashMap<>(); -> Option A

4. Quick Check:

   Memo cache = Map for key-value pairs [OK]

Hint: Use Map for key-value memo cache in Java [OK]

Common Mistakes:

• Using List instead of Map for memoization
• Incorrect array declaration syntax
• Using Set which stores only keys, no values

3. What will be the output of the following Java code using memoization for Fibonacci numbers?

import java.util.*;
public class FibMemo {
  static Map memo = new HashMap<>();
  public static int fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    int result = fib(n-1) + fib(n-2);
    memo.put(n, result);
    return result;
  }
  public static void main(String[] args) {
    System.out.println(fib(5));
  }
}

medium

A. Error at runtime

B. 8

C. 5

D. 13

Solution

1. Step 1: Understand Fibonacci sequence calculation

   fib(5) = fib(4) + fib(3), and so on, with base cases fib(0)=0, fib(1)=1.

2. Step 2: Calculate fib(5) with memoization

   fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5. Memoization avoids repeated calls but result is same.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci(5) = 5, memoization doesn't change result [OK]

Common Mistakes:

• Confusing Fibonacci values for wrong n
• Assuming memoization changes output
• Thinking code causes runtime error

4. Identify the error in this Java memoized factorial function:

import java.util.*;
public class FactorialMemo {
  static Map memo = new HashMap<>();
  public static int fact(int n) {
    if (n == 0) return 1;
    if (memo.containsKey(n)) return memo.get(n);
    int result = n * fact(n - 1);
    memo.put(n, result);
    return result;
  }
  public static void main(String[] args) {
    System.out.println(fact(-1));
  }
}

medium

A. Memo map is not initialized properly

B. fact method should return long instead of int

C. Incorrect multiplication order in recursion

D. No base case for negative input causes infinite recursion

Solution

1. Step 1: Analyze base cases and input handling

   Base case handles n == 0 only, but negative n causes no stop condition.

2. Step 2: Effect of negative input

   Calling fact(-1) leads to infinite recursion because n never reaches 0 or memoized value.

3. Final Answer:

   No base case for negative input causes infinite recursion -> Option D

4. Quick Check:

   Missing negative base case = infinite recursion [OK]

Hint: Check base cases cover all input ranges [OK]

Common Mistakes:

• Ignoring negative input handling
• Assuming memo initialization error
• Thinking multiplication order causes error

5. You want to optimize a recursive function that calculates the number of ways to climb n stairs taking 1 or 2 steps at a time. Which memoization approach below correctly implements this in Java?

hard

A. Use a List<Integer> to store results; always calculate recursively without checking cache.

B. Use a Map to store results; check cache before recursive calls; store results after calculation.

C. Use an int array without initializing values; store results only after all recursion ends.

D. Use a Set<Integer> to store visited stairs; return size of set as result.

Solution

1. Step 1: Understand problem and memoization needs

   We must store number of ways for each stair number to avoid repeated calculations.

2. Step 2: Evaluate memoization approaches

   Use a Map to store results; check cache before recursive calls; store results after calculation. uses Map to store and check results before recursion, which is correct memoization practice.

3. Final Answer:

   Use a Map to store results; check cache before recursive calls; store results after calculation. -> Option B

4. Quick Check:

   Memo = Map with cache check and store [OK]

Hint: Check cache before recursion, store after calculation [OK]

Common Mistakes:

• Not checking cache before recursive calls
• Using List or Set incorrectly for memoization
• Storing results too late or not at all