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.kt

fun fib(n: Int, memo: HashMap<Int, Int>): Int {
	if (memo.containsKey(n)) {
		return memo[n]!!
	}
	if (n < 2) {
		memo[n] = n
		return n
	}
	val value = fib(n - 1, memo) + fib(n - 2, memo)
	memo[n] = value
	return value
}

fun main() {
	val memo = HashMap<Int, Int>()
	val result = fib(6, memo)
	println(result)
}

Complexity

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

Implementation notes

Kotlin: the recursion takes the memo as a HashMap<Int, Int> argument rather than a companion object field, which keeps state explicit without hiding the lesson behind a shared global. The containsKey + !! indexer pair stays parallel to the lesson spec instead of leaning on getOrPut.
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 `HashMap<Int, Int>` keyed by `n` stores each completed subproblem. Before recursing, check `memo.containsKey(n)`: a hit returns immediately, a miss descends.

explicit memo state The memo is threaded through the recursion as `memo: HashMap<Int, Int>` so the lesson stays about caching, not global state.