Memoization to Optimize Recursion in DSA Go - Execution Trace

Concept Flow - Memoization to Optimize Recursion

Start Recursive Call

↓

Check if Result in Memo?

Yes→Return Memoized Result

No↓

Compute Result Recursively

↓

Store Result in Memo

↓

Return Result

The flow shows how recursion checks for stored results before computing, saving time by reusing answers.

Execution Sample

DSA Go

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]
}

This Go function calculates Fibonacci numbers using recursion with memoization to avoid repeated work.

Execution Table

Step	Operation	n	Memo Before	Memo After	Returned Value	Visual Memo State
1	Call fib(4)	4	{}	{"4": ?}	?	{"4": ?}
2	Call fib(3)	3	{"4": ?}	{"3": ?}	?	{"4": ?, "3": ?}
3	Call fib(2)	2	{"4": ?, "3": ?}	{"2": ?}	?	{"4": ?, "3": ?, "2": ?}
4	Call fib(1)	1	{"4": ?, "3": ?, "2": ?}	{"4": ?, "3": ?, "2": ?, "1": 1}	1	{"4": ?, "3": ?, "2": ?, "1": 1}
5	Call fib(0)	0	{"4": ?, "3": ?, "2": ?, "1": 1}	{"4": ?, "3": ?, "2": ?, "1": 1, "0": 0}	0	{"4": ?, "3": ?, "2": ?, "1": 1, "0": 0}
6	Compute fib(2) = fib(1)+fib(0)	2	{"4": ?, "3": ?, "2": ?, "1": 1, "0": 0}	{"4": ?, "3": ?, "2": 1, "1": 1, "0": 0}	1	{"4": ?, "3": ?, "2": 1, "1": 1, "0": 0}
7	Call fib(1) (memo hit)	1	{"4": ?, "3": ?, "2": 1, "1": 1, "0": 0}	Same	1	{"4": ?, "3": ?, "2": 1, "1": 1, "0": 0}
8	Compute fib(3) = fib(2)+fib(1)	3	{"4": ?, "3": ?, "2": 1, "1": 1, "0": 0}	{"4": ?, "3": 2, "2": 1, "1": 1, "0": 0}	2	{"4": ?, "3": 2, "2": 1, "1": 1, "0": 0}
9	Call fib(2) (memo hit)	2	{"4": ?, "3": 2, "2": 1, "1": 1, "0": 0}	Same	1	{"4": ?, "3": 2, "2": 1, "1": 1, "0": 0}
10	Compute fib(4) = fib(3)+fib(2)	4	{"4": ?, "3": 2, "2": 1, "1": 1, "0": 0}	{"4": 3, "3": 2, "2": 1, "1": 1, "0": 0}	3	{"4": 3, "3": 2, "2": 1, "1": 1, "0": 0}
11	Return final result fib(4)	4	{"4": 3, "3": 2, "2": 1, "1": 1, "0": 0}	Same	3	{"4": 3, "3": 2, "2": 1, "1": 1, "0": 0}
12	Exit	-	-	-	-	All results memoized, recursion ends

💡 All Fibonacci values up to 4 computed and stored; recursion ends.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 10	Final
n	-	1	2	3	4	4
memo	{}	{"1":1, "0":0}	{"1":1, "0":0, "2":1}	{"1":1, "0":0, "2":1, "3":2}	{"1":1, "0":0, "2":1, "3":2, "4":3}	{"1":1, "0":0, "2":1, "3":2, "4":3}
returned_value	-	1	1	2	3	3

Key Moments - 3 Insights

Why does the function check the memo map before computing fib(n)?

Because if fib(n) is already in memo (see steps 7 and 9), it returns immediately, avoiding repeated work and saving time.

What happens when n is 0 or 1 in the recursion?

At steps 4 and 5, the function returns n directly as base cases, storing these in memo to use later.

How does memoization reduce the number of recursive calls?

By storing results after first computation (steps 6, 8, 10), later calls reuse these values (steps 7, 9), preventing duplicate calls.

Visual Quiz - 3 Questions

Look at the execution table at step 6, what value is stored in memo for n=2?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Memo After' and 'Visual Memo State' columns at step 6.

At which step does the function return a memoized value for n=1?

A Step 7

B Step 9

C Step 4

D Step 10

💡 Hint

Look for 'memo hit' in the Operation column and n=1.

If memoization was not used, how would the number of calls change?

A Same number of calls

B Fewer calls, faster execution

C More calls, repeated calculations

D No calls at all

💡 Hint

Refer to key moment about how memoization avoids repeated work.

Concept Snapshot

Memoization stores results of recursive calls in a map.
Before computing fib(n), check if result exists.
If yes, return stored result to save time.
If no, compute recursively and store result.
This avoids repeated calculations and speeds up recursion.

Full Transcript

Memoization is a technique to optimize recursion by saving results of function calls. When the function is called with a value, it first checks if the answer is already stored in a map called memo. If yes, it returns that answer immediately, skipping extra work. If not, it computes the answer recursively, stores it in memo, and returns it. This process reduces repeated calculations, making recursion faster and more efficient. The example code calculates Fibonacci numbers using this method. The execution table shows each step, how memo grows, and when stored results are reused. Key moments explain why memo checks happen first, how base cases work, and how memoization cuts down calls. The quiz tests understanding of memo values, memo hits, and the effect of memoization on recursion calls.

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