Memoization to Optimize Recursion in DSA Go

Mental Model

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

Analogy: Like writing down answers in a notebook so you don't repeat the same homework twice.

fib(5)
  ↓
fib(4) + fib(3)
 ↓       ↓
fib(3)+fib(2) fib(2)+fib(1)
 ↑ memo stores results to reuse

Dry Run Walkthrough

Input: Calculate fib(5) using recursion with memoization

Goal: Find fib(5) efficiently by saving results of fib(3), fib(2), etc. to avoid repeated work

Step 1: Call fib(5), not in memo, so compute fib(4) + fib(3)

memo = {}
fib(5) -> fib(4) + fib(3)

Why: We start by breaking fib(5) into smaller problems

Step 2: Call fib(4), not in memo, compute fib(3) + fib(2)

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

Why: We break fib(4) further to smaller fib numbers

Step 3: Call fib(3), not in memo, compute fib(2) + fib(1)

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

Why: Keep breaking down until base cases

Step 4: Call fib(2), not in memo, compute fib(1) + fib(0)

memo = {}
fib(2) -> fib(1) + fib(0)

Why: Reach base cases fib(1)=1 and fib(0)=0

Step 5: fib(1) and fib(0) are base cases, return 1 and 0

memo = {}
fib(1)=1, fib(0)=0

Why: Base cases stop recursion

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

memo = {2:1}

Why: Save fib(2) to avoid recomputing

Step 7: fib(1) base case returns 1

memo = {2:1}

Why: fib(1) is base case

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

memo = {2:1, 3:2}

Why: Save fib(3) for reuse

Step 9: Call fib(2), found in memo as 1, reuse value

memo = {2:1, 3:2}

Why: Avoid recomputing fib(2)

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

memo = {2:1, 3:2, 4:3}

Why: Save fib(4) for reuse

Step 11: Call fib(3), found in memo as 2, reuse value

memo = {2:1, 3:2, 4:3}

Why: Avoid recomputing fib(3)

Step 12: Calculate fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store in memo

memo = {2:1, 3:2, 4:3, 5:5}

Why: Final answer stored

Result:

memo = {2:1, 3:2, 4:3, 5:5}
Final fib(5) = 5

Annotated Code

DSA Go

package main

import "fmt"

func fib(n int, memo map[int]int) int {
    if val, found := memo[n]; found {
        return val // reuse saved result
    }
    if n <= 1 {
        return n // base case
    }
    result := fib(n-1, memo) + fib(n-2, memo) // recursive calls
    memo[n] = result // save result
    return result
}

func main() {
    memo := make(map[int]int)
    n := 5
    result := fib(n, memo)
    fmt.Printf("fib(%d) = %d\n", n, result)
}

if val, found := memo[n]; found { return val // reuse saved result }

Check if result already computed to avoid repeated work

if n <= 1 { return n // base case }

Return base case values 0 or 1

result := fib(n-1, memo) + fib(n-2, memo) // recursive calls

Compute fib(n) by summing smaller fib values

memo[n] = result // save result

Store computed result for future reuse

Output

fib(5) = 5

Complexity Analysis

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

Space: O(n) for the memo map storing results and recursion call stack

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 as base case

DSA Go

if n <= 1 {
        return n // base case
    }

n = 1 (small input)

Returns 1 immediately as base case

DSA Go

if n <= 1 {
        return n // base case
    }

Repeated calls with same n

Uses memo to return saved result instantly

DSA Go

if val, found := memo[n]; found {
        return val // reuse saved result
    }

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 result 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 saves results of recursive calls to avoid repeating work.

Use it when recursion solves the same subproblems multiple times.

The key is to remember results so you never solve the same problem twice.

Practice

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

easy

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

B. To make the function run slower by adding extra steps

C. To remove recursion and use loops instead

D. To increase the memory usage without any benefit

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so they don't need to be recalculated.

2. Step 2: Identify the benefit of memoization

   By reusing saved results, the function runs faster and avoids repeated work.

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 work by caching results [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with removing recursion
• Ignoring the memory benefit of caching

2. Which of the following Go code snippets correctly declares a memo map for memoization of integer keys and values?

easy

A. memo := new(map[int]int)

B. memo := make(map[int]int)

C. memo := make([]int, 10)

D. memo := map[string]int{}

Solution

1. Step 1: Identify correct map declaration syntax

   In Go, make(map[int]int) creates a map with int keys and int values.

2. Step 2: Check other options

   memo := map[string]int{} uses string keys, not int; memo := make([]int, 10) creates a slice, not a map; memo := new(map[int]int) creates a pointer to a map but does not initialize it.

3. Final Answer:

   memo := make(map[int]int) -> Option B

4. Quick Check:

   Correct map syntax = make(map[int]int) [OK]

Hint: Use make(map[int]int) to create int-to-int map [OK]

Common Mistakes:

• Using slice instead of map for memo
• Using wrong key type in map
• Declaring pointer to map without initialization

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

package main
import "fmt"

func fib(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

func main() {
    memo := make(map[int]int)
    fmt.Println(fib(5, memo))
}

medium

A. 8

B. Error

C. 3

D. 5

Solution

1. Step 1: Understand Fibonacci calculation with memo

   fib(5) = fib(4) + fib(3), and memo stores intermediate results to avoid repeats.

2. Step 2: Calculate fib(5) step-by-step

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Memoized fib(5) returns 5 quickly [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memo and recalculating
• Expecting error due to map usage

4. Identify the error in this Go recursive function with memoization for factorial:

func fact(n int, memo map[int]int) int {
    if n == 0 {
        return 1
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = n * fact(n-1, memo)
    return memo[n]
}

func main() {
    memo := make(map[int]int)
    fmt.Println(fact(-1, memo))
}

medium

A. Compilation error due to map usage

B. No error, output is 1

C. Infinite recursion for negative input

D. Returns 0 for negative input

Solution

1. Step 1: Analyze base case and input

   Base case is n == 0, but input is -1, so base case never reached.

2. Step 2: Understand recursion behavior

   For n = -1, function calls fact(-2), then fact(-3), causing infinite recursion.

3. Final Answer:

   Infinite recursion for negative input -> Option C

4. Quick Check:

   Negative input causes infinite recursion [OK]

Hint: Check base case covers all inputs to avoid infinite recursion [OK]

Common Mistakes:

• Assuming negative input returns 1
• Ignoring infinite recursion possibility
• Expecting compilation error incorrectly

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 using memoization in Go. Which approach below correctly applies memoization to avoid repeated calculations?

hard

A. Pass a map[int]int as a parameter to the function and store intermediate results in it

B. Use a slice of size n and fill it after recursion completes

C. Use a global variable to store results and update it inside the function

D. Call the recursive function twice without storing results

Solution

1. Step 1: Understand memoization with parameters

   Passing a map as a parameter allows storing and reusing results during recursion.

2. Step 2: Evaluate options for memoization

   Pass a map[int]int as a parameter to the function and store intermediate results in it correctly uses a map parameter; Use a global variable to store results and update it inside the function uses global state which is less safe; Use a slice of size n and fill it after recursion completes fills after recursion, not during; Call the recursive function twice without storing results repeats work without memo.

3. Final Answer:

   Pass a map[int]int as a parameter to the function and store intermediate results in it -> Option A

4. Quick Check:

   Memo map parameter stores intermediate results [OK]

Hint: Pass memo map as argument to cache results during recursion [OK]

Common Mistakes:

• Using global variables instead of parameters
• Filling memo after recursion ends
• Not storing results causing repeated work