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

import scala.collection.mutable.HashMap

object Main {
	def fib(n: Int, memo: HashMap[Int, Int]): Int = {
		if (memo.contains(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
		value
	}

	def main(args: Array[String]): Unit = {
		val memo = HashMap.empty[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

Scala: the recursion takes the memo as a scala.collection.mutable.HashMap[Int, Int] argument rather than a companion-object var, which keeps state explicit without hiding the lesson behind a shared global. The contains + apply indexer pair stays parallel to the lesson spec instead of leaning on getOrElseUpdate.
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.contains(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.