Fibonacci with Memoization

Compute fib(n) recursively. Cache each fib(k) in a memo map so each subproblem is solved at most once.

Algorithm

Canonical input n = 6 produces fib(6) = 8. Replay highlights every memo write and every cache hit.

Basic Implementation

basic.go

package main

import "fmt"

var memo = map[int]int{}

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

func main() {
	result := fib(6)
	fmt.Println(result)
	fmt.Println(memo)
}

Complexity

Time: O(n) with memoization (vs. O(2^n) without)
Space: O(n) memo + O(n) call stack

Implementation notes

Go: a package-level memo := map[int]int{} plus the v, ok := memo[n] comma-ok pattern keeps the memo lookup and write visible without hiding the lesson behind a closure.
The replay shows the call stack on one side and the memo map on the other so memo writes and cache hits are visually distinct.

memoization A `map[int]int` keyed by `n` stores each completed subproblem. Before recursing, check `memo[n]`: a hit returns immediately, a miss descends.

explicit memo state The memo is a package-level `map` so the recursion stays about caching, not parameter passing.