Fibonacci with Memoization

Compute fib(n) recursively and cache each fib(k) in a memo map so each subproblem is solved at most once. Turns exponential recursion into a linear walk, the canonical introduction to dynamic programming.

Algorithm

Canonical input n = 6 produces fib(6) = 8. The replay shows the descent for fib(6) -> fib(5) -> ... -> fib(0) then four cache hits on the unwind (one per repeat-call subproblem).

Basic Implementation

basic.dart

int fib(int n, Map<int, int> memo) {
  final cached = memo[n];
  if (cached != null) {
    return cached;
  }
  if (n < 2) {
    memo[n] = n;
    return n;
  }
  final value = fib(n - 1, memo) + fib(n - 2, memo);
  memo[n] = value;
  return value;
}

void main() {
  final memo = <int, int>{};
  final result = fib(6, memo);
  print(result);
  print(memo);
}

Complexity

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

Implementation notes

Dart: pass memo explicitly as a Map<int, int>. Reading via final cached = memo[n]; keeps the cache hit branch visible. The Map.update shortcut would hide the memo write.
The replay shows each fib(k) call and the memo state after, marking the cache-hit steps distinctly so the viewer can count how many descents were avoided.

memoization Reuse cached subproblem results instead of re-descending.