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

using System;
using System.Collections.Generic;

class Program {
	static int Fib(int n, Dictionary<int, int> memo) {
		if (memo.ContainsKey(n)) {
			return memo[n];
		}
		if (n < 2) {
			memo[n] = n;
			return n;
		}
		int value = Fib(n - 1, memo) + Fib(n - 2, memo);
		memo[n] = value;
		return value;
	}

	static void Main() {
		Dictionary<int, int> memo = new Dictionary<int, int>();
		int result = Fib(6, memo);
		Console.WriteLine(result);
	}
}

Complexity

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

Implementation notes

C#: the recursion takes the memo as a Dictionary<int, int> argument rather than a static field, which keeps state explicit without hiding the lesson behind a thread-static slot. The if (memo.TryGetValue(n, out int v)) pattern is left out so the ContainsKey + indexer pair stays parallel to the lesson spec.
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 `Dictionary<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 `Dictionary<int, int> memo` so the lesson stays about caching, not global state.